5. Longest Palindromic Substring

Most people reach for a DP table on this one because it lives in the dynamic programming pattern set — but the table costs $O(n^2)$ space you don’t need. Growing a palindrome outward from its center gets the same time bound with constant space, and the reason it works is worth a minute.

The problem

Given a string s, find the longest contiguous slice of it that reads the same forward and backward. If several tie for longest, any one of them is accepted. (Full statement on LeetCode.)

For "babad", both "bab" and "aba" are valid answers. For "cbbd", it’s "bb".

Intuition: every palindrome has a center

A palindrome is symmetric, so it’s fully described by its middle plus how far it reaches. Fix that middle and you can rebuild the whole thing: compare the characters one step out on each side, and keep going while they match. The moment they differ — or you fall off an end — you’ve found the widest palindrome anchored there.

There’s one wrinkle. Odd-length palindromes like "aba" sit on a single character, but even-length ones like "bb" sit between two characters. So each index is really two candidate centers: one on the character, one in the gap to its right. A string of length $n$ has $2n-1$ possible centers, and checking each takes at most $O(n)$ work, which is where the $O(n^2)$ comes from.

Why prefer this over the DP table? Both are $O(n^2)$ time, but the table carries an $n \times n$ boolean grid the whole way through. Expanding from centers keeps nothing but the best window seen so far.

Solution

Try both centers at every index, and remember the widest window:

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        int start = 0, end = 0;  // best window found so far

        for (int center = 0; center < s.length(); center++) {
            int odd  = expand(s, center, center);     // centered on a character
            int even = expand(s, center, center + 1); // centered between two characters
            int len = Math.max(odd, even);
            if (len > end - start + 1) {
                start = center - (len - 1) / 2;
                end = center + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    // Grow outward while both ends match; return the palindrome's length.
    private 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;  // ends overshot by one on each side
    }
}

The right - left - 1 catches people off guard. When the loop stops, left and right have each stepped one past the palindrome, so the real bounds are left + 1 and right - 1. Its length is (right - 1) - (left + 1) + 1, which is just right - left - 1.

Complexity

Approach	Time	Space
Expand around center	$O(n^2)$	$O(1)$
DP table	$O(n^2)$	$O(n^2)$

Same asymptotic time, but the center approach spends no extra memory. (Manacher’s algorithm gets this to $O(n)$ time, but it’s rarely expected in an interview and easy to get wrong under pressure.)

In an interview

Say the key sentence early: “a palindrome is defined by its center, so I’ll expand from each of the $2n-1$ centers.” That framing tells the interviewer you understand why, not just that you memorized a grid. The trap everyone hits is forgetting even-length palindromes — if you only expand from (center, center), "cbbd" returns "b" instead of "bb". Calling expand a second time with center + 1 is the whole fix.

If they push for the DP framing, it’s the same recurrence the pattern hub drills: a substring s[i..j] is a palindrome when its ends match and the inside s[i+1..j-1] already is. The counting cousin, Palindromic Substrings, reuses this exact expand helper — solve one and you’ve solved both.

References

• LeetCode 5 — Longest Palindromic Substring