LeetCode 5 – Longest Palindromic Substring

The trap in Longest Palindromic Substring is that the obvious framing — "check every substring" — leads to an O(n³) solution, and the textbook fix is a dynamic-programming table that costs O(n²) memory. The answer you actually want in an interview is neither: expand around each centre, O(n²) time and O(1) space, and it is about fifteen lines.

The problem

Given a string, return the longest contiguous substring that reads the same forwards and backwards. Substring, not subsequence — the characters have to be adjacent.

Input:  "babad"      Output: "bab"     ("aba" is equally valid)
Input:  "cbbd"       Output: "bb"      an even-length palindrome
Input:  "abcdzdcab"  Output: "cdzdc"

The key observation: count the centres, not the substrings

A string of length n has O(n²) substrings, so enumerating them is already too slow before you have verified a single one. But every palindrome has a centre, and there are only 2n - 1 possible centres:

n odd-length centres, one on each character — "aba" is centred on the b.
n - 1 even-length centres, one in each gap between characters — "abba" is centred between the two bs.

Forgetting the even case is the single most common bug in this problem, and it is a quiet one: the code still runs and still returns a palindrome, just never an even-length one. Test with "cbbd" — it must return "bb", not "b".

From each centre, push two pointers outwards while the characters match. The moment they differ, or a pointer falls off the end, that centre is finished. Every palindrome in the string is found exactly once, from its own centre.

The off-by-one that bites everyone

The expansion loop exits after both pointers have already stepped one position too far. So when lo and hi come out of the loop, the palindrome is the range [lo + 1, hi - 1], and its length is hi - lo - 1 — not hi - lo + 1. Write the loop, then derive that expression on the whiteboard rather than guessing it.

Having expand return only the length keeps it a pure function, which is worth the small amount of arithmetic it costs at the call site. Given a length and the centre index i, the substring begins at i - (len - 1) / 2, and integer division makes that one expression cover both centre shapes: an odd palindrome of length 2k + 1 starts at i - k, and an even one of length 2k starts at i - k + 1.

Java

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            int odd = expand(s, i, i);         // centred on i
            int even = expand(s, i, i + 1);    // centred between i and i + 1
            int len = Math.max(odd, even);

            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;     // works for both centre shapes
            }
        }

        return s.substring(start, start + maxLen);
    }

    /** Length of the longest palindrome expanding outwards from this centre. */
    private 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;   // both pointers stepped one past the palindrome
    }
}

Keep the state in local variables, not fields. Hanging start and maxLen off the instance is a tempting way to avoid the arithmetic above, and it makes the method return a stale answer the second time it is called on the same object. Interviewers notice.

The even-length call expand(s, i, i + 1) is safe on the last index without a bounds check: hi starts at s.length(), the loop condition rejects it immediately, and the resulting length of 0 never beats maxLen.

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(lo: int, hi: int) -> int:
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
                lo -= 1
                hi += 1
            return hi - lo - 1              # both stepped one past the palindrome

        start, max_len = 0, 0
        for i in range(len(s)):
            length = max(expand(i, i), expand(i, i + 1))
            if length > max_len:
                max_len = length
                start = i - (length - 1) // 2

        return s[start:start + max_len]

The DP version, and why it is the weaker answer

The interval-DP formulation is worth being able to write, because the same shape solves Longest Palindromic Subsequence and Palindrome Partitioning II. Let dp[i][j] mean "the range i..j is a palindrome". Then

dp[i][j] = s[i] == s[j] AND (j - i < 2 OR dp[i + 1][j - 1])

Because dp[i][j] depends on dp[i + 1][j - 1], the outer loop has to run i downwards so the inner range is already computed. Getting that direction wrong reads perfectly and returns nonsense.

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = Math.min(n, 1);

    for (int i = n - 1; i >= 0; i--) {          // downwards: dp[i + 1][...] must be ready
        dp[i][i] = true;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}

Complexity

Approach	Time	Space
Check every substring	`O(n³)`	`O(1)`
Interval DP	`O(n²)`	`O(n²)`
Expand around centre	`O(n²)`	`O(1)`
Manacher's algorithm	`O(n)`	`O(n)`

Expanding around centres is worst-case O(n²) — a string of one repeated character makes every centre expand the whole way — but it beats the DP on space and is far quicker to write correctly.

Manacher's algorithm gets it to linear time by reusing the palindrome radii already computed inside a known palindrome, so a mirrored position starts from a lower bound instead of zero. Know that it exists and what it costs. Almost no interviewer expects you to reproduce it, and offering "there is an O(n) solution, Manacher's, but I would write the centre expansion unless you want the linear one" is the answer that lands.

What the interviewer is checking

That you find the centres instead of enumerating substrings.
That you handle even-length palindromes — "cbbd" is the test.
That you derive hi - lo - 1 rather than guessing the length.
Empty string and single character return themselves without a special case.
That you know a linear solution exists, even if you do not write it.