Longest Palindromic Substring

Find the longest substring of a string that reads the same forwards and backwards. The brute force is O(n³), the dynamic-programming table is O(n²) time and O(n²) space, and expand-around-centre is O(n²) time and O(1) space, which makes the DP solution strictly worse despite being the one people reach for.

Written against Java 17.

The problem

"babad"  -> "bab"    or "aba"; both are length 3
"cbbd"   -> "bb"
"a"      -> "a"
"ac"     -> "a"      or "c"

Note that a substring is contiguous, where a subsequence is not. That distinction changes the problem entirely — the longest palindromic subsequence is a different question with a different answer.

Expand around centre

static String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";

    int start = 0, maxLength = 1;

    for (int i = 0; i < s.length(); i++) {
        int odd = expand(s, i, i);        // centred on a character
        int even = expand(s, i, i + 1);   // centred between two characters
        int longest = Math.max(odd, even);

        if (longest > maxLength) {
            maxLength = longest;
            start = i - (longest - 1) / 2;
        }
    }
    return s.substring(start, start + maxLength);
}

private static int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;              // the length that was still valid
}

O(n²) time in the worst case, a string of all identical characters, and O(1) extra space.

There are 2n−1 centres

This is the part that gets missed, a palindrome of odd length has a character at its centre; one of even length has a gap between two characters. "aba" is centred on b; "abba" is centred between the two bs.

Checking only expand(s, i, i) finds every odd-length palindrome and no even-length one, so "cbbd" returns "c" instead of "bb". The bug passes any test whose answer happens to be odd, and "babad", the canonical example, is one of them.

So each index contributes two centres, giving 2n−1 in total across the string, and both have to be tried at every position.

The right - left - 1 and the start calculation

Two off-by-ones, and both come from the same source: the loop exits after the pointers have moved one step too far.

expand returns right - left - 1 rather than right - left + 1. When the loop stops, left is one before the palindrome’s first character and right one after its last. The span between them is right - left + 1 inclusive, minus the two invalid ends, which is right - left - 1.

The start calculation i - (longest - 1) / 2 covers both parities in one expression. For an odd length of 5 centred at i, the start is i - 2, and (5 - 1) / 2 is 2. For an even length of 4 centred between i and i + 1, the start is i - 1, and (4 - 1) / 2 is 1 by integer division. Integer truncation is doing the parity handling, which is neat and worth a comment in real code because it is not obvious.

The dynamic-programming solution, and why not

static String longestPalindromeDp(String s) {
    int n = s.length();
    boolean[][] isPalindrome = new boolean[n][n];
    int start = 0, maxLength = 1;

    for (int i = 0; i < n; i++) isPalindrome[i][i] = true;

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            int j = i + length - 1;

            if (s.charAt(i) != s.charAt(j)) continue;
            if (length == 2 || isPalindrome[i + 1][j - 1]) {
                isPalindrome[i][j] = true;
                if (length > maxLength) {
                    maxLength = length;
                    start = i;
                }
            }
        }
    }
    return s.substring(start, start + maxLength);
}

The recurrence is clean: s[i..j] is a palindrome when the ends match and the interior is one. Iterating by length rather than by index is required, because the interior must be solved before the whole.

It is O(n²) time, the same as expand-around-centre, and O(n²) space, which is 10 GB of booleans for a string of 100,000 characters. There is no version of this problem where the DP solution is the better choice; it is worth knowing because it is the natural DP framing, and worth rejecting on the space.

Manacher’s algorithm

O(n) exists. Manacher’s algorithm interleaves separators ("aba" becomes "#a#b#a#") so every palindrome is odd-length, then reuses previously computed radii through a mirror argument to avoid re-expanding.

It is roughly forty lines, hard to write from memory, and rarely required: n would have to be in the millions for the difference from O(n²) to matter. Knowing it exists and what it does is usually the right depth; implementing it from memory in an interview is a signal about preparation rather than ability.

Complexity, honestly

The O(n²) worst case for expand-around-centre needs a string of identical characters, where every centre expands the full width. On ordinary text most centres fail on the first comparison, so the observed behaviour is close to linear.

That is worth saying because the DP solution has no such best case, it fills the whole table regardless of input. Two algorithms with the same asymptotic bound can differ by a large constant and by their behaviour on realistic data.

Edge cases

• Empty or null, return "" rather than throwing. The guard is one line.
• Single character: a palindrome of length 1; maxLength starting at 1 handles it.
• No palindrome longer than 1: "ac"; the first character is returned, which is correct and arbitrary between the two.
• All identical characters, the worst case, and the one to benchmark against.
• Unicode: charAt returns a UTF-16 code unit, so a character outside the basic plane is two units and a naive reversal can split a surrogate pair. For emoji or historic scripts, iterate code points.

The Unicode case is the one most solutions ignore, and it is the one that matters outside an interview.

Related shapes

The expand-around-centre move applies to any “find the longest region with a symmetric property” question. Counting all palindromic substrings is the same loop, adding the number of successful expansions rather than tracking a maximum:

static int countPalindromes(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += countFrom(s, i, i) + countFrom(s, i, i + 1);
    }
    return count;
}

private static int countFrom(String s, int left, int right) {
    int found = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        found++;
        left--;
        right++;
    }
    return found;
}

Every successful expansion is itself a distinct palindrome, so counting them is the whole change.

The same structure also answers “the longest palindromic prefix”, by expanding only from centres near the start and keeping the result that reaches index 0, which is the core of the shortest-palindrome problem, where the answer is the reversed suffix prepended to the original.

The centre-expansion idea is a cousin of the sliding window — both grow a region from a starting point and stop when a condition fails. The table-based alternative here is the same machinery as the 0/1 knapsack, which is where that space cost is worth paying. More in the algorithms guides.

Frequently asked questions

Why are there 2n−1 centres?

A palindrome of odd length is centred on a character and one of even length between two. Checking only single-character centres misses "bb" entirely.

What is the time complexity of expand-around-centre?

O(n²) worst case, O(1) extra space, the worst case needs a string of identical characters; ordinary text is much faster.

Why is the DP solution worse?

Same O(n²) time, but O(n²) space, a 100,000-character string needs about 10 GB. It also fills the whole table regardless of input.

Why does expand return right - left - 1?

The loop exits after both pointers have moved one step past the valid palindrome, so two positions must be subtracted from the inclusive span.

How does i - (longest - 1) / 2 handle both parities?

Integer truncation. An odd length of 5 gives 2 and an even length of 4 gives 1, which are the correct offsets from the respective centres.

Is there a linear solution?

Manacher’s algorithm, at O(n). It is about forty lines and rarely needed: n has to be in the millions before it beats the simpler solution in practice.

Substring or subsequence?

Substring means contiguous. The longest palindromic subsequence is a different problem with a different answer and a genuine DP solution.

What should an empty string return?

"". Guard for null and empty at the top; both are one line.

How do I count all palindromic substrings instead?

The same loop, adding the number of successful expansions from each centre rather than tracking the longest.

Does this handle emoji correctly?

No. charAt returns UTF-16 code units, so characters outside the basic plane are two units. Iterate code points if the input can contain them.