Topics › Strings › Medium String Problems

Longest Palindrome in a string

Medium TUF ID 2852 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given a string s, return its longest substring (a contiguous block of characters) that reads the same forwards and backwards. If several palindromic substrings share the maximum length, return the one that starts first. (LeetCode accepts any of them; fixing the leftmost one makes the answer deterministic and lets every approach be tested against the same expected output.)

Constraints: 1 ≤ n ≤ 1000 on LeetCode, digits and English letters. The Java methods also accept the empty string and return "".

Example 1

s = "babad"
answer = "bab"        // "aba" is just as long, but "bab" starts earlier

Example 2

s = "cbbd"
answer = "bb"         // the longest palindrome here has even length

Example 3

s = "abc"
answer = "a"          // every single character is a palindrome of length 1

Do not confuse this with the longest palindromic subsequence, where characters may be skipped. In "axbya" the longest palindromic subsequence has length 3 ("axa", "aba" or "aya"), while no contiguous block longer than one letter is a palindrome, so the longest palindromic substring is just "a".

Approach 1: Brute force, test every substring

Intuition. There are only n(n+1)/2 substrings. Enumerate each one by its start i and end j, check whether it is a palindrome with two pointers moving inward, and remember the longest. The check costs up to O(n), so the whole thing is cubic.

A cheap optimisation keeps the code honest: we only run the palindrome check when the candidate is strictly longer than the best so far. That never changes the answer, and because we try starts from left to right, the strict > also guarantees that the leftmost of several equally long palindromes is the one we keep.

Algorithm.

1. For every start i and every end j ≥ i:
2. If j - i + 1 beats the best length and s[i..j] is a palindrome, record (i, length).
3. Return s.substring(bestStart, bestStart + bestLen).

static String bruteForce(String s) {
    int n = s.length(), bestStart = 0, bestLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int len = j - i + 1;
            if (len > bestLen && isPalindrome(s, i, j)) {   // strict '>' keeps the leftmost on ties
                bestStart = i;
                bestLen = len;
            }
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

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

Complexity. Time O(n^3): O(n^2) substrings, each checked in up to O(n) steps. Space O(1) besides the returned string: we store indices, never build the substrings we test.

The length filter helps on friendly inputs, but it gives no guarantee: a check can match many outer pairs before failing, and nothing stops that from happening for a quadratic number of candidates. The real waste is that overlapping substrings share their inner comparisons, and the brute force repeats them every time.

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

Intuition. The brute force re-checks the same inner characters over and over. When it tests s[2..8], it compares s[3] with s[7], s[4] with s[6], which is exactly the check it already did for s[3..7]. The fix is the key structural fact about palindromes:

s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome.

The inside is shorter, so if we fill a boolean table pal[i][j] in order of increasing length, the inside is always already known. Lengths 1 and 2 are the base cases: they have no real inside, so only s[i] == s[j] matters (for length 1 that is trivially true).

Algorithm.

1. For len = 1 .. n, for every start i with j = i + len - 1 < n:
2. pal[i][j] = (s[i] == s[j]) && (len <= 2 || pal[i+1][j-1]).
3. If it is a palindrome and longer than the best, record it. Within one length, starts are visited left to right, so the first one found of the maximum length is the leftmost.

static String better(String s) {
    int n = s.length(), bestStart = 0, bestLen = 0;
    boolean[][] pal = new boolean[n][n];
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            pal[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || pal[i + 1][j - 1]);
            if (pal[i][j] && len > bestLen) {
                bestStart = i;
                bestLen = len;
            }
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

Complexity. Time O(n^2): each of the n(n+1)/2 cells is computed in O(1). Space O(n^2) for the table, about one million booleans for n = 1000.

This is a classic interval DP and worth knowing because the same table answers other questions (for example “is s[i..j] a palindrome?” for palindrome partitioning). But for this problem the table is overkill, because each cell is only ever read once, by the cell one step outward.

Approach 3: Optimal, expand around every centre

Intuition. Turn the DP around. Instead of asking “is this range a palindrome?”, stand at a centre and grow outwards for as long as the two ends match. Every palindrome has a centre:

• Odd length ("aba"): the centre is a character. There are n such centres.
• Even length ("abba"): the centre is the gap between two characters. There are n - 1 such centres.

From a fixed centre, the palindromes are nested: if the window of radius r fails, every larger window around the same centre fails too (it contains the failed pair at the same mirrored positions). So expanding until the first mismatch finds the longest palindrome around that centre, and checking all 2n - 1 centres finds the global answer. This is the DP recurrence walked along one diagonal, with no table needed.

Algorithm.

1. For each index c, compute odd = expand(c, c) and even = expand(c, c + 1).
2. expand(lo, hi) moves lo left and hi right while both are in range and s[lo] == s[hi]. When it stops, the last valid window was lo+1 .. hi-1, whose length is hi - lo - 1.
3. Convert a length back to a start: an odd palindrome of length L around c starts at c - L/2; an even one around the gap after c starts at c - L/2 + 1.
4. Keep the longest with a strict >. Two equally long palindromes have the same parity, and the one with the smaller centre starts earlier, so the leftmost wins.

static String optimal(String s) {
    int n = s.length(), bestStart = 0, bestLen = 0;
    for (int c = 0; c < n; c++) {
        int odd = expand(s, c, c);              // centre on a character: "aba"
        int even = expand(s, c, c + 1);         // centre between two characters: "abba"
        if (odd > bestLen) {
            bestLen = odd;
            bestStart = c - odd / 2;
        }
        if (even > bestLen) {
            bestLen = even;
            bestStart = c - even / 2 + 1;
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

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":

Complexity. Time O(n^2) in the worst case: there are 2n - 1 centres and each expansion takes up to O(n) steps (the all-a string hits this bound). In practice most expansions stop after a step or two. Space O(1).

This is the answer interviewers expect: quadratic time, constant space, and about fifteen lines.

Approach 4: Manacher’s algorithm, linear time

Intuition. Expand-around-centre wastes work in one specific way. Suppose we already know a long palindrome spanning [L, R] with centre C, and we are now at a position i inside it. The palindrome is a mirror, so the neighbourhood of i looks exactly like the neighbourhood of its mirror 2C - i, at least up to the boundary R. We already computed the radius at the mirror, so we can start i at min(R - i, rad[mirror]) instead of at zero, and only try to grow beyond R.

To avoid handling odd and even centres separately, insert a separator between characters: "abba" becomes "|a|b|b|a|". Every palindrome in the new string has odd length and a real centre, and a palindrome of radius r in the new string corresponds to a palindrome of length exactly r in s (a maximal one starts and ends on separators, so of its 2r + 1 characters, r + 1 are separators and r are letters).

Algorithm.

1. Build t of length 2n + 1 with '|' at even positions and the letters of s at odd positions.
2. Maintain centre and right: the palindrome found so far that reaches furthest to the right.
3. For each i: if i < right, start rad[i] at min(right - i, rad[2*centre - i]). Then expand while the characters match. If i + rad[i] passes right, update centre and right.
4. The largest rad (leftmost on ties) gives the length; its start in s is (i - rad) / 2.

static String manacher(String s) {
    int n = s.length();
    if (n == 0) return "";
    char[] t = new char[2 * n + 1];            // "abc" -> "|a|b|c|": every palindrome in t has odd length
    for (int i = 0; i < t.length; i++) t[i] = (i % 2 == 0) ? '|' : s.charAt(i / 2);
    int[] rad = new int[t.length];             // rad[i] = how far the palindrome centred at i reaches on each side
    int centre = 0, right = 0;                 // the palindrome reaching furthest right is t[2*centre-right .. right]
    int bestCentre = 0;
    for (int i = 0; i < t.length; i++) {
        if (i < right) rad[i] = Math.min(right - i, rad[2 * centre - i]);   // copy from the mirror, capped at the boundary
        while (i - rad[i] - 1 >= 0 && i + rad[i] + 1 < t.length && t[i - rad[i] - 1] == t[i + rad[i] + 1]) rad[i]++;
        if (i + rad[i] > right) {
            centre = i;
            right = i + rad[i];
        }
        if (rad[i] > rad[bestCentre]) bestCentre = i;
    }
    int start = (bestCentre - rad[bestCentre]) / 2;   // rad in t equals the palindrome's length in s
    return s.substring(start, start + rad[bestCentre]);
}

Complexity. Time O(n). Every successful expansion step pushes right one position further, and right never moves left, so all the inner while loops together run at most 2n + 1 times. Space O(n) for t and rad.

Manacher is rarely required in interviews, but it is the only approach here that handles n = 10^6 comfortably, and the mirror trick (reuse information from inside the current best window) is the same idea that powers the Z-function.

Edge cases and pitfalls

• Even-length answers. "cbbd" has answer "bb". Forgetting the gap centres (or the length-2 base case in the DP) returns "c".
• Empty and single-character strings. "" returns "" and "a" returns "a". Initialising bestLen = 0 and returning a substring of length bestLen handles both without special cases; Manacher returns early for the empty string only to make that case obvious to the reader.
• Off-by-one in expand. The loop exits one step past the palindrome, so the length is hi - lo - 1, not hi - lo + 1.
• Ties. Use a strict > when updating, and visit candidates from left to right, if you want a deterministic answer.
• Building substrings in the brute force. Writing new StringBuilder(sub).reverse().equals(sub) for every substring adds O(n) allocation per check and makes the cubic solution even slower. Compare characters in place.
• Substring vs subsequence. If skipping characters is allowed, this becomes a DP on two indices (longest common subsequence of s and its reverse), a different problem with a different answer.

Related problems

• Longest Palindromic Substring is the same problem as listed in the A2Z sheet.
• Palindromic Substrings counts all palindromic substrings with the same expand-around-centre idea.
• Longest palindromic subsequence is the version where characters may be skipped.
• Minimum insertions to make string palindrome looks for the longest palindromic prefix instead of the longest palindrome anywhere.
• Z function reuses earlier work inside a window, just like Manacher’s mirror step.