Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return the longest contiguous substring that reads the same forwards and backwards. Brute force checks every substring in O(n³). The interview-grade answer is expand-around-center: treat each index (and each gap between indices) as a possible palindrome center and grow outward while characters match — O(n²) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you avoid the naive 'enumerate every substring and test it' and instead exploit the structural symmetry of a palindrome to prune the search to centers.
Where candidates slip
Forgetting even-length palindromes — only expanding from single-character centers, which misses 'abba'. Or rebuilding the substring inside the loop, turning O(n²) into O(n³).
How to stand out
Derive 2n−1 centers out loud, track indices not strings, and name Manacher's O(n) as the theoretical ceiling without pretending you'd code it under time pressure.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewLongest palindromic SUBSTRINGSubstring or subsequence?SubsequenceSubstringExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Check Every Substring
1Hint 1Explore hintHide hint
The most literal reading: a palindrome is a substring, so enumerate every substring and test each one. How many substrings are there, and how long does one palindrome check take?
2Hint 2Explore hintHide hint
There are ~n²/2 substrings (choose a start and an end). Verifying one substring is a palindrome takes O(n) with two pointers.
3Hint 3Explore hintHide hint
Two nested loops pick start i and end j; a helper walks inward from both ends to confirm the palindrome. Track the longest valid (i, j).
A · Core idea
Enumerate every substring s[i..j], check whether it is a palindrome with a two-pointer walk, and remember the longest one that passes.
Why this is the honest starting point. The problem literally says 'find a substring with property P'. The zero-insight version of any such problem is: list all substrings, test the property on each, keep the best. It's correct and trivial to reason about, which is exactly why it's worth stating before optimizing — it pins down the baseline you're about to beat.
Where the waste lives. The killer is that checking s[i..j] from scratch throws away everything you learned checking s[i+1..j-1]. A palindrome of length 7 contains a palindrome of length 5 at its core — but brute force re-verifies that core every single time. That redundant inner work is the O(n) factor we're paying on top of the O(n²) pairs, and it's precisely what the next approach removes.
Why we don't ship it. For n = 1000, O(n³) is 10⁹ operations — borderline TLE and clearly signalling you didn't see the structure. State it, give the complexity, then pivot: 'every palindrome is built around a center, so let's grow from centers instead of testing arbitrary endpoints.'
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "cbbd"Array state
lo=1, hi=2
s[1]='b' == s[2]='b' → match, move inward
"bb"C · Code with teaching comments
Reference implementation previewpublic String longestPalindrome(String s) { int n = s.length(); String best = ""; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) {Explore the full codeHide the full code
D · Why it works and complexityO(n³) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The redundancy is the whole story: a palindrome and its inner palindrome share a center. Brute force ignores that shared structure and re-checks the middle over and over. Recognizing that overlap is the bridge to both expand-around-center and the DP table.
ComplexityO(n³) time, O(1) space — O(n²) substrings × O(n) to verify each = O(n³). No auxiliary structure, so O(1) extra space.
E · Edge cases and pitfalls4s = "a" — Only pair is (0,0); isPalindrome returns true; best = "a". Single character handled.Explore edge casesHide edge cases
Edge cases handled
s = "a"Only pair is (0,0); isPalindrome returns true; best = "a". Single character handled.
Pitfalls
- Rebuilding s.substring on every pass even when it can't beat best — wasteful allocations.
- Off-by-one in the inner loop: j must start at i, not i+1, or you lose single-character answers.
- Skipping the length guard, so you pay the O(n) verify on substrings that can't possibly win.
Approach 2 of 2 · Optimal
Expand Around Center (Optimal for n ≤ 1000)
1Hint 1Explore hintHide hint
Brute force re-checks shared cores. What if you started AT the core instead? Every palindrome is symmetric around a middle point — anchor there and grow outward.
2Hint 2Explore hintHide hint
There are two kinds of centers: a single character (odd length, like 'aba') and a gap between two characters (even length, like 'abba'). That's 2n−1 centers total.
3Hint 3Explore hintHide hint
From each center, move two pointers outward while they stay in bounds and the characters match. The widest successful expansion across all centers is the answer.
A · Core idea
For each of the 2n − 1 possible centers, push two pointers outward while the characters match and stay in bounds. Whenever an expansion beats the best length seen so far, record its start and length. Slice the answer out once at the end.
The mental shift that unlocks this. Brute force asks 'is this arbitrary substring a palindrome?' — there are n²/2 substrings and verifying each is O(n). Expand-around-center flips the question: 'how far does the palindrome centered here reach?' Because a palindrome is defined by symmetry around a midpoint, fixing the midpoint and growing is a single uninterrupted walk — the moment two characters disagree, no wider palindrome shares this center, so you stop. You never re-verify an inner core because you built outward from it.
Why 2n − 1 centers and not n. Odd-length palindromes ('aba') are centered on a character. Even-length palindromes ('abba') are centered on the gap between two characters — there is no single middle character. There are n character-centers and n−1 gap-centers, hence 2n − 1. Miss the gap-centers and you silently fail every even-length answer like 'cbbd' → 'bb'. The clean way to handle both is to call the same expand helper twice per index: once with (i, i) and once with (i, i+1).
Why we track indices, not the substring. It's tempting to keep best = s.substring(...) inside the loop, but that copies up to O(n) characters every time you improve — and in the worst case ('aaaa...') you improve O(n) times, dragging the work back toward O(n³) on the allocation axis. Storing just start and maxLen keeps the inner loop O(1) per step; you materialize the string exactly once at the return.
The ceiling, briefly. Manacher's algorithm reuses palindrome information across centers to hit true O(n). It's worth naming so the interviewer knows you know it exists, but coding it from memory under pressure is a needless risk when n ≤ 1000 makes O(n²) trivially fast.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "babad"Array state
l=1, r=1
center on 'a' — trivially matches itself
"bab"C · Code with teaching comments
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The whole speedup comes from never throwing away the symmetric core. Brute force re-checks the middle of every candidate; center-expansion makes the middle the starting point, so each character pair is compared a bounded number of times. When a 'find the longest X substring' problem has a property that grows symmetrically (or monotonically) from a point, anchoring on that point and expanding is almost always the unlock.
ComplexityO(n²) time, O(1) space — 2n−1 centers, each expansion is at most O(n) → O(n²) time. We store only a start index and a length, so O(1) extra space.
E · Edge cases and pitfalls5s = "cbbd" — Odd centers all give length 1. The even center between indices 1 and 2 expands 'bb' to length 2 → returns "bb". Proves even-centers are required.Explore edge casesHide edge cases
Edge cases handled
s = "cbbd"Odd centers all give length 1. The even center between indices 1 and 2 expands 'bb' to length 2 → returns "bb". Proves even-centers are required.s = "aaaa"Every expansion succeeds; best grows to the full string. We improve O(n) times but each store is O(1), so still O(n²) overall and O(1) space.
Pitfalls
- Only calling expand(i, i) and skipping expand(i, i+1) — silently misses every even-length palindrome.
- Returning r - l + 1 instead of r - l - 1 — forgetting the loop overshoots by one on both sides.
- Storing the substring instead of (start, len) inside the loop — extra O(n) copies on each improvement.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, maxLen = 1; for (int i = 0; i < s.length(); i++) { int odd = expand(s, i, i);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Forgetting even-length centers
Expanding only from (i, i) handles odd palindromes ('aba') but never the gap between two characters, so 'cbbd' wrongly returns a length-1 answer instead of 'bb'.
Explore the code comparisonHide the code comparison
Forgetting even-length centers
Expanding only from (i, i) handles odd palindromes ('aba') but never the gap between two characters, so 'cbbd' wrongly returns a length-1 answer instead of 'bb'.
Don't write this
for (int i = 0; i < n; i++) {
int len = expand(s, i, i); // odd only!
if (len > maxLen) { ... }
}Write this instead
for (int i = 0; i < n; i++) {
int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
if (len > maxLen) { ... }
}2Wrong length after expansion
The while loop stops only after l and r have each stepped one past the palindrome. The valid span is [l+1, r-1], whose length is (r-1)-(l+1)+1 = r - l - 1, not r - l + 1.
Explore the code comparisonHide the code comparison
Wrong length after expansion
The while loop stops only after l and r have each stepped one past the palindrome. The valid span is [l+1, r-1], whose length is (r-1)-(l+1)+1 = r - l - 1, not r - l + 1.
Don't write this
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l + 1 # overcounts by 2Write this instead
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 13Recovering start with the wrong formula
Given a center i and final length, the left edge is i - (len - 1) / 2. Using len / 2 breaks for odd lengths and shifts the substring left by one.
Explore the code comparisonHide the code comparison
Recovering start with the wrong formula
Given a center i and final length, the left edge is i - (len - 1) / 2. Using len / 2 breaks for odd lengths and shifts the substring left by one.
Don't write this
start = i - len / 2;Write this instead
start = i - (len - 1) / 2;Revise
Carry the pattern into the interview
Pattern to remember
Expand around center — every palindrome has a middle
Code pattern to memorize
for center in range(2n - 1):
l, r = center // 2, center // 2 + center % 2
while l >= 0 and r < n and s[l] == s[r]:
l -= 1; r += 1
# palindrome is s[l+1 : r]Rules to remember
- 1There are 2n − 1 centers, not n — every gap between two characters is also a center (for even-length palindromes).
- 2Expand while
s[l] == s[r]and both pointers are in bounds; the answer iss[l+1 : r]after the loop overshoots by one. - 3Track only the best start and length, not the substring itself — slice once at the end to avoid O(n) copies inside the loop.
- 4A DP table is also O(n²) but costs O(n²) space — expand-around-center is strictly better, so lead with it.
- 5Manacher's algorithm is the O(n) answer; name it, don't code it unless explicitly pushed — it's rarely expected.
Use this pattern when
- Find the longest / count palindromic substrings of a string
- The property is symmetric and grows from a middle point outward
- You can verify a candidate by walking two pointers from a center
- n is small enough (≤ ~1000) that O(n²) passes comfortably
Choose another pattern when
- Subsequence, not substring → that's Longest Palindromic Subsequence (interval DP)
- Need true O(n) under a tight constraint → Manacher's, not center expansion
- Checking a single fixed string is a palindrome → just two pointers, no scan
- Partitioning into palindromes → backtracking + palindrome DP
Interview takeaway
Palindromes are defined by their center, not their ends. The moment you anchor on the middle and grow outward, an O(n³) substring-enumeration problem collapses to O(n²) with no extra memory. The same center-expansion trick solves Palindromic Substrings (count) and underlies Manacher's.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCenter-Expansion for Palindromes. Whenever a problem hinges on contiguous symmetry around a midpoint, anchor on the 2n−1 centers and grow outward. Same engine powers Palindromic Substrings (counting) and is the brute-force baseline Manacher's optimizes.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Palindromic SubstringsSame center expansion, but COUNT every successful expansion instead of tracking the longest.
- Longest Palindromic SubsequenceSubsequence, not substring — interval DP on dp[i][j], O(n²) time and space.
- Palindrome PartitioningComing soonBacktracking that cuts the string into palindromes; precompute an isPal DP table to prune.
- Shortest PalindromeComing soonFind the longest palindromic PREFIX, then KMP/rolling-hash to prepend the minimal characters.