Longest Palindromic Substring

1. Problem & Core Objective

Return the longest palindromic substring (contiguous) of s.

s = "babad"   →  "bab"   (or "aba" — either is accepted)
s = "cbbd"    →  "bb"

Constraints: 1 <= s.length <= 1000 · letters and digits

What's actually being tested: that expand-around-centre beats the DP table here — O(1) space instead of O(n²), same time. It's the question in this section where the tabulated DP is not the best answer, and knowing why matters more than knowing the DP.

2. First-Principles Thought Process

Every palindrome has a centre

A palindrome reads the same both ways, so it's symmetric about a centre. That centre is either:

• a character — odd length, like "aba" centred on b
• a gap between characters — even length, like "abba" centred between the two bs

There are n character-centres and n − 1 gap-centres, so 2n − 1 centres in total.

Expand from each centre

From a centre, walk outward while the characters match. The moment they differ — or you run off either end — that centre's longest palindrome is complete.

Each expansion is O(n) and there are O(n) centres, so O(n²) time and O(1) space.

The DP alternative, and why it's worse here

isPal[i][j] is true when s[i..j] is a palindrome:

isPal[i][j] = (s[i] == s[j]) && (j - i < 3 || isPal[i+1][j-1])

That's O(n²) time and O(n²) space — a million booleans at n = 1000.

Same time, worse space. The DP earns its place when the palindrome table is queried repeatedly — which is exactly Palindrome Partitioning, not this question.

The even/odd trap

Handling only odd-length centres finds "aba" but misses "bb". Both centre types must be tried at every position.

for (int i = 0; i < n; i++) {
    expand(s, i, i);        // odd — centred on a character
    expand(s, i, i + 1);    // even — centred on the gap after it
}

Forgetting the even case fails on "cbbd", returning a single character.

3. Solution Paths

Approach 1 — Check every substring (brute force)

public String longestPalindrome(String s) {
    String best = "";
    for (int i = 0; i < s.length(); i++)
        for (int j = i; j < s.length(); j++)
            if (isPalindrome(s, i, j) && j - i + 1 > best.length())
                best = s.substring(i, j + 1);
    return best;
}

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

• Time O(n³) · Space O(1)

Counter-questions on this approach

⭐ "Where does the cubic come from?"

O(n²) substrings, each checked in O(n). At n = 1000 that's 10^9 character comparisons — too slow.

And it's redundant: checking s[i..j] re-examines the interior that s[i+1..j-1] already covered. Both the DP and expand-around-centre exploit that overlap; this version doesn't.

⭐ "Could you at least skip substrings shorter than the current best?"

Yes, and it helps in practice — iterate lengths descending and return the first palindrome found, or skip when j - i + 1 <= best.length(). Both prune heavily on typical input.

Neither changes the O(n³) worst case, which is a string like "aaaa…a" where every substring is a palindrome and nothing is pruned.

"Is substring inside the loop a problem?"

It allocates O(length) per call. Tracking (start, length) and materialising once at the end is strictly better — a constant-factor issue, but free to fix.

Approach 2 — DP table

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

    for (int i = 0; i < n; i++) isPal[i][i] = true;          // single characters

    for (int len = 2; len <= n; len++)                        // by increasing length
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s.charAt(i) != s.charAt(j)) continue;
            if (len == 2 || isPal[i + 1][j - 1]) {
                isPal[i][j] = true;
                if (len > maxLen) { start = i; maxLen = len; }
            }
        }
    return s.substring(start, start + maxLen);
}

• Time O(n²) · Space O(n²)

Counter-questions on this approach

⭐ "Why iterate by length rather than by index?"

Because isPal[i][j] depends on isPal[i+1][j-1] — a shorter interval. Filling by increasing length guarantees the inner value is ready.

Iterating i and j in the natural nested order would read cells not yet computed. Getting the fill order right is the tabulation-specific obligation that memoisation handles automatically.

⭐ "Why len == 2 || in the condition?"

Because a length-2 palindrome has no interior to check — isPal[i+1][j-1] would be isPal[i+1][i], an inverted range that's meaningless.

With "bb", i = 0, j = 1, so the interior would be isPal[1][0]. The len == 2 short-circuit handles it before that read happens.

Some implementations write j - i < 3 instead, which covers lengths 2 and 3 together — a length-3 palindrome also needs no interior check, since its middle character is trivially palindromic.

⭐ "It's O(n²) time like expand-around-centre. So why prefer the other?"

Space. This allocates n² booleans — a million at n = 1000, which is 1 MB. Expand-around-centre is O(1).

Same time, strictly worse space, and more code. The table is worth building only when you'll query it repeatedly — which is Palindrome Partitioning, not this problem.

That's the honest reason to know both: the DP isn't wrong here, it's just not the right tool.

Approach 3 — Expand around centre (optimal)

public String longestPalindrome(String s) {
    int start = 0, maxLen = 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 on the gap after it
        int len = Math.max(odd, even);

        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;              // recover the left edge
        }
    }
    return s.substring(start, start + maxLen);
}

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 overshot by one
}

Trace — s = "babad", centre i = 2 (the second a):

• Time O(n²) · Space O(1)

Counter-questions on this approach

⭐ "Why hi - lo - 1 for the length?"

Because the loop exits after both pointers have moved one step past the palindrome — lo is one left of the start, hi one right of the end.

So the palindrome spans lo+1 .. hi-1, whose length is (hi-1) - (lo+1) + 1 = hi - lo - 1.

It's worth deriving rather than memorising: on "aba" the loop ends with lo = -1, hi = 3, giving 3 - (-1) - 1 = 3 ✓

⭐ "Explain start = i - (len - 1) / 2."

i is the centre index and len is the palindrome's length; the left edge is (len-1)/2 characters before the centre.

Integer division makes this work for both parities. Odd length 3 centred at i: (3-1)/2 = 1, so start = i - 1 ✓. Even length 4 with centres i and i+1: (4-1)/2 = 1, so start = i - 1 ✓ — because the even expansion started at (i, i+1), and the left half extends one further from i.

That the same formula covers both cases is a genuine convenience, not an accident — and it's the line most likely to be wrong, so I'd check it on a length-2 example: "bb" at i = 0 gives len = 2, start = 0 - 0 = 0 ✓.

⭐ "Why must both expand(i, i) and expand(i, i+1) be called?"

Because palindromes come in both parities and they have different centre types. Odd-length ones are centred on a character; even-length ones on a gap.

Calling only the odd version finds "aba" but misses "bb" entirely — on "cbbd" it would return a single character instead of "bb".

There are n character-centres and n−1 gap-centres, hence 2n − 1 total.

"Does expand(s, i, i+1) overflow at the last index?"

No — the loop guard checks hi < s.length() before indexing, so when i = n−1 the condition fails immediately and it returns hi - lo - 1 = n - (n-1) - 1 = 0. A zero-length result that never wins the max.

"What's the worst case?"

A string of identical characters, like "aaaa…a". Every centre expands the full width, so it's genuinely O(n²) — 10^6 at n = 1000, which is fine.

"Is there anything faster?"

Manacher's algorithm is O(n). It reuses information from previously computed centres, exploiting the symmetry of the palindrome already found. It's genuinely linear but substantially harder to write correctly, and at n = 1000 the O(n²) version runs in about a millisecond. Worth naming, not worth writing.

Comparison

4. Why the Optimal Wins

Against the cubic version: both the DP and expansion exploit that a palindrome's interior is itself a palindrome, so the O(n) re-check disappears.

Against the DP: identical time, but O(1) space instead of O(n²). The table stores the palindromic status of every interval when the question asks for just one — the longest.

The DP isn't wrong, it's over-built for this question. It becomes the right tool in Palindrome Partitioning, where isPal[i][j] is queried repeatedly during a search.

The framing worth keeping:

Every palindrome has a centre — a character or a gap — so there are 2n − 1 centres. Expand from each while the characters match. O(n²) time, O(1) space, and both parities must be tried.

5. Java Prerequisites

Expand-around-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 overshot by one
}

Both parities, every position

expand(s, i, i);        // odd
expand(s, i, i + 1);    // even

Recovering the start — start = i - (len - 1) / 2, correct for both parities by integer division.

Track indices, not strings — build the substring once at the end rather than allocating inside the loop.

6. Interview Communication Guide

Clarifying questions: Substring (contiguous) or subsequence (substring)? If several are tied for longest, any of them (yes)? Is a single character a palindrome (yes)? Case-sensitive (assume yes)?

The pitch

"Every palindrome is symmetric about a centre, and that centre is either a character for odd lengths or a gap between characters for even ones. So there are 2n − 1 centres.

From each, I expand outward while the characters match, stopping at the first mismatch or either edge. Each expansion is O(n) and there are O(n) centres, so O(n²) time and O(1) space.

Both parities must be tried at every position. Handling only character-centres finds 'aba' but misses 'bb' — on 'cbbd' it would return a single character.

I'd mention the DP alternative because it's the expected answer for this section: isPal[i][j] = s[i] == s[j] && isPal[i+1][j-1], filled by increasing length so the shorter interval is ready. That's also O(n²) time but O(n²) space — a million booleans at n = 1000.

Same time, worse space, more code. The table is worth building when you'll query it repeatedly, which is Palindrome Partitioning — not here, where you want one answer.

Two details in the expansion. The length is hi - lo - 1 because both pointers overshoot by one when the loop exits. And the start is i - (len-1)/2, which works for both parities thanks to integer division — worth checking on a length-2 case rather than trusting.

There's an O(n) solution, Manacher's, which reuses symmetry from previously computed centres. It's genuinely linear but hard to write correctly, and at n = 1000 the quadratic version runs in about a millisecond."

Edge cases to volunteer:

Name "cbbd". It's the minimal case that fails without the even-centre expansion, and a solution missing it returns a single character while passing "babad".

7. Follow-Up Questions — Modified Constraints

⭐ "Count all palindromic substrings instead of finding the longest."

Question 6. Same expansion, but count each successful step rather than tracking a maximum — every widening of a centre is one more palindrome. O(n²) time, O(1) space, and the change is a single line.

⭐ "Find the longest palindromic SUBSEQUENCE."

A completely different problem — LeetCode 516. Subsequences needn't be contiguous, so there's no centre to expand from. It's a 2-D DP: dp[i][j] = dp[i+1][j-1] + 2 when the ends match, else max(dp[i+1][j], dp[i][j-1]). O(n²) time and space. Worth naming that "substring" and "subsequence" change the algorithm entirely.

"Return all longest palindromic substrings when there are ties."

Collect every centre achieving the maximum length in a second pass, or track a list during the first. O(n²) still; the output could be O(n) strings.

"What if n were 10^5?"

O(n²) is 10^10 — too slow. Manacher's O(n) becomes necessary. That's the threshold where the harder algorithm earns its complexity.

"Find the longest palindrome you can make by deleting at most k characters."

Much harder — it's the longest palindromic subsequence with a budget, an O(n² k) DP. The centre-expansion idea doesn't survive deletions.

"Check whether the whole string can be rearranged into a palindrome."

Not a substring problem at all — count character frequencies and check that at most one is odd. O(n). Worth mentioning because it sounds related and shares nothing.