☕ DSA Java Articles

Topics › Strings › Medium String Problems

Longest Palindromic Substring

Medium TUF ID 638 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, return the longest substring of s that is a palindrome, that is, reads the same forwards and backwards. A substring is contiguous; this is not the subsequence problem. If several palindromic substrings share the maximum length, any of them is accepted by the judge; the methods in the Java file all return the leftmost one so that they can be compared against each other exactly.

Constraints: 1 ≤ |s| ≤ 1000; s consists of digits and English letters. The Java file also handles the empty string, returning "".

Example 1

s = "babad"
answer = "bab"          // "aba" is also a longest palindrome; we return the leftmost

Example 2

s = "cbbd"
answer = "bb"           // even length palindromes count too

Example 3

s = "forgeeksskeegfor"
answer = "geeksskeeg"

Approach 1: Brute force, test every substring

Intuition. There are n(n + 1) / 2 substrings; check each one with a two-pointer palindrome test and remember the longest. A small pruning helps a lot in practice: skip the test when the substring is not longer than the best found so far, because it could not improve the answer anyway. Iterating starts from left to right and using a strict > means the leftmost of several longest palindromes wins.

Algorithm.

  1. Set bestStart = 0, bestLen = 0.
  2. For every i, for every j ≥ i: if j - i + 1 > bestLen and s[i..j] is a palindrome, record it.
  3. Return s.substring(bestStart, bestStart + bestLen).
static String bruteForce(String s) {
    int n = s.length();
    int bestStart = 0, bestLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (j - i + 1 > bestLen && isPalindrome(s, i, j)) {
                bestStart = i;
                bestLen = j - i + 1;
            }
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

private static boolean isPalindrome(String s, int i, int j) {
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++;
        j--;
    }
    return true;
}

Complexity. Time O(n^3): O(n^2) substrings, O(n) per check. Space O(1).

Approach 2: Better, a table of which substrings are palindromes

Intuition. The brute force re-examines the same inner characters over and over. Observe that s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome (a string of length 0 or 1 is always one). This is a recurrence on intervals, so store dp[i][j] = "s[i..j] is a palindrome" and fill it in order of increasing length: the inner interval is two shorter, hence already computed.

Algorithm.

  1. Allocate boolean[n][n]; set bestStart = 0, bestLen = 1.
  2. For len from 1 to n, for every start i with j = i + len - 1 < n:
    • If s[i] != s[j] the entry stays false.
    • Otherwise dp[i][j] = (len <= 2) || dp[i+1][j-1].
    • If dp[i][j] and len > bestLen, record the interval.
  3. Return the recorded substring.
static String better(String s) {
    int n = s.length();
    if (n == 0) return "";
    boolean[][] dp = new boolean[n][n];
    int bestStart = 0, bestLen = 1;
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s.charAt(i) != s.charAt(j)) continue;
            dp[i][j] = len <= 2 || dp[i + 1][j - 1];
            if (dp[i][j] && len > bestLen) {
                bestStart = i;
                bestLen = len;
            }
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

Complexity. Time O(n^2): each table cell is filled in constant time. Space O(n^2) for the table, which is the weakness: a million booleans for n = 1000, far more than the problem needs.

Approach 3: Optimal, expand around every centre

Intuition. Turn the recurrence inside out. Every palindrome has a centre: a single character for odd length, the gap between two characters for even length. Starting from a centre and moving two pointers outwards, the substring stays a palindrome exactly as long as the two characters match; the first mismatch tells us the longest palindrome with that centre. There are n odd centres and n - 1 even centres, so 2n - 1 expansions in total, each O(n) at worst, and no table.

The index arithmetic: expand returns the palindrome length. For an odd palindrome of length L centred at c, the start is c - L / 2. For an even palindrome of length L centred between c and c + 1, the start is c - L / 2 + 1.

Algorithm.

  1. Set bestStart = 0, bestLen = 1.
  2. For each c: compute odd = expand(c, c) and even = expand(c, c + 1); if either exceeds bestLen, record the new start and length.
  3. Return the recorded substring.
static String optimal(String s) {
    int n = s.length();
    if (n == 0) return "";
    int bestStart = 0, bestLen = 1;
    for (int c = 0; c < n; c++) {
        int odd = expand(s, c, c);                     // odd length, centred on s[c]
        if (odd > bestLen) {
            bestLen = odd;
            bestStart = c - odd / 2;
        }
        int even = expand(s, c, c + 1);                // even length, centred between s[c] and s[c + 1]
        if (even > bestLen) {
            bestLen = even;
            bestStart = c - even / 2 + 1;
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

private static int expand(String s, int lo, int hi) {
    while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
        lo--;
        hi++;
    }
    return hi - lo - 1;
}

Dry run on s = "babad":

c odd expansion even expansion bestLen, bestStart
0 b → 1 b vs a → 0 1, 0
1 a, then b..b → 3 a vs b → 0 3, 0 (“bab”)
2 b, then a..a → 3, then b vs d stops b vs a → 0 3, 0 (not longer)
3 a, then b vs d stops → 1 a vs d → 0 3, 0
4 d → 1 runs off the end → 0 3, 0

Complexity. Time O(n^2) in the worst case (a string of identical letters makes every centre expand to an edge), but typically much faster since most expansions stop immediately. Space O(1).

Approach 4: Manacher’s algorithm, linear time

Intuition. Expansion around centres wastes work when palindromes overlap. Suppose we know a big palindrome centred at center reaching to index right. For a centre i inside it, its mirror image mirror = 2 * center - i has already been processed, and by symmetry the palindrome at i is at least as long as the one at mirror, capped by the distance to right. So we start expanding at i from that radius instead of from zero.

Two details make this clean. First, insert a separator # between characters and sentinels ^ and $ at the ends; every palindrome in the transformed string t then has odd length, so one array p[i] (the radius at t[i]) covers both parities, and the sentinels stop the expansion without bounds checks. Second, a radius of p[i] in t corresponds to a palindrome of length p[i] in s, starting at (i - p[i]) / 2.

Why linear: every iteration of the inner while that succeeds pushes right further to the right, and right never decreases, so there are at most |t| = O(n) successful comparisons in total, plus one failing comparison per centre.

Algorithm.

  1. Build t = ^#s0#s1#...#s(n-1)#$.
  2. For each i from 1 to |t| - 2: if i < right, set p[i] = min(right - i, p[mirror]); expand while the characters at i ± (p[i] + 1) match; if the new palindrome reaches beyond right, update center and right; track the largest p[i].
  3. Return s.substring(start, start + bestLen) with start = (bestCenter - bestLen) / 2.
static String manacher(String s) {
    int n = s.length();
    if (n == 0) return "";
    char[] t = new char[2 * n + 3];                    // ^ # s0 # s1 # ... # s(n-1) # $
    t[0] = '^';
    t[2 * n + 2] = '$';
    for (int i = 0; i < n; i++) {
        t[2 * i + 1] = '#';
        t[2 * i + 2] = s.charAt(i);
    }
    t[2 * n + 1] = '#';
    int m = t.length;
    int[] p = new int[m];                              // p[i] = radius of the palindrome centred at t[i]
    int center = 0, right = 0;                         // the palindrome reaching furthest right so far
    int bestLen = 0, bestCenter = 0;
    for (int i = 1; i < m - 1; i++) {
        int mirror = 2 * center - i;
        if (i < right) p[i] = Math.min(right - i, p[mirror]);
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        if (p[i] > bestLen) {
            bestLen = p[i];
            bestCenter = i;
        }
    }
    int start = (bestCenter - bestLen) / 2;            // radius in t equals length in s
    return s.substring(start, start + bestLen);
}

Complexity. Time O(n). Space O(n) for t and p.

Manacher’s algorithm is rarely required in interviews for n ≤ 1000, but it is the right tool when n reaches 10^5 or more, and being able to explain why centre expansion is quadratic in the worst case is worth as much as the code.

Edge cases and pitfalls