Run it
Expansion from both kinds of centre with each one's result printed, then the odd-only version failing on an even-length palindrome, and a brute-force check for agreement.
Expand around centres
Every palindrome has a centre. There are 2n−1 possible centres — n single characters for odd-length palindromes, and n−1 gaps between characters for even-length ones. Expand outwards from each.
O(n²) time, O(1) space.
The two centre types are the detail that gets forgotten. Checking only (i, i) finds "aba" and misses "abba" entirely, because an even-length palindrome has no single central character.
The lo + 1, hi - lo - 1 adjustment accounts for the loop having stepped one past the valid range on both sides — a small off-by-one worth deriving carefully rather than guessing.
The dynamic programming alternative
dp[i][j] is True when s[i..j] is a palindrome:
dp[i][j] = (s[i] == s[j]) and (j − i < 2 or dp[i+1][j−1])
O(n²) time and O(n²) space — strictly worse than expanding around centres, which achieves the same time in O(1) space.
Worth knowing because it makes the substructure explicit, and because the same table answers related questions such as counting all palindromic substrings. For this specific problem, expand-around-centre is the better answer.
Why 2n − 1 centres
An odd-length palindrome like aba is centred on a character. An even-length one like abba is centred on the gap between two. So there are n character centres and n − 1 gap centres.
Forgetting the even case is the classic bug here: the code passes on racecar and fails on abba, which is exactly the sort of half-correct that survives a quick test.
Why not dynamic programming
The DP formulation — dp[i][j] is true when s[i:j+1] is a palindrome — is also O(n²) time and additionally O(n²) space. Expanding around centres gets the same time in O(1) space and is shorter to write.
Mention the DP version, then say why you are not using it. Recognising that two solutions share a time bound and differ on space is the judgement being tested.
The O(n) answer, and when to mention it
Manacher's algorithm is O(n): it reuses the palindromes already found to skip work, in the same spirit as KMP's prefix table. It is long, fiddly, and almost never expected.
Name it, say it exists and that you would look it up rather than reconstruct it under time pressure. That reads as calibration; attempting it from memory and stalling does not.
Manacher's algorithm
The O(n) solution. It is rarely expected in an interview, and knowing it exists is worth a sentence.
The idea: while expanding around centres, information from previously computed palindromes can be reused. If a centre lies inside a larger palindrome already found, its mirror position's radius gives a lower bound, so expansion can start from there rather than from zero.
Combined with a clever handling of odd and even lengths — interleaving separator characters so every palindrome becomes odd-length — it achieves linear time.
| Approach | Time | Space | Practical |
|---|
| Brute force | O(n³) | O(1) | No |
| Dynamic programming | O(n²) | O(n²) | Rarely |
| Expand around centres | O(n²) | O(1) | Yes |
| Manacher's | O(n) | O(n) | Only if asked |
The honest answer in an interview: offer expand-around-centre, state that Manacher's achieves O(n), and mention that it is complex enough that you would look it up rather than reproduce it from memory. That is a more credible position than attempting it and getting it wrong.
Edge cases
| Case | Result |
|---|
"" | "" |
| Single character | That character |
All identical, "aaaa" | The whole string |
No palindrome longer than 1, "abcd" | Any single character |
Even-length answer, "cbbd" | "bb" — requires the even centre |
| Whole string is a palindrome | The whole string |
| Several equal-length answers | Any one; confirm which is expected |
The "cbbd" row is the test that catches implementations handling only odd centres.
Count all palindromic substrings. Same expansion, but count every successful expansion rather than tracking the maximum. O(n²).
Longest palindromic subsequence. Not contiguous, so a different DP — and it equals the longest common subsequence of the string and its reverse, which is a neat reduction worth knowing.
Minimum insertions to make a palindrome. Length minus the longest palindromic subsequence.
Palindrome partitioning. Split the string into the fewest palindromic pieces — DP over the palindrome table.
Shortest palindrome by prepending characters. Solved with KMP's failure function on s + separator + reversed(s), which is an unexpected and elegant connection.
What it is testing
Do you handle both centre types? The single most common failure.
Do you reach O(1) space? The DP solution is correct and uses O(n²) space; expand-around-centre is the improvement.
Do you get the index arithmetic right? Returning the substring requires careful start and length computation after the loop overshoots.
Do you know substring means contiguous? Answering the subsequence problem is a different, and wrong, answer.
Are you honest about Manacher's? Mentioning it and declining to write it from memory is a better signal than a broken attempt.
Recap in one screen
- Every palindrome has a centre; there are 2n−1 of them, counting gaps for even lengths.
- Expand outwards from each centre and keep the longest — O(n²) time, O(1) space.
- Handling only single-character centres misses all even-length palindromes.
- The DP table is O(n²) in both time and space, so it is strictly worse here.
- Manacher's is O(n) by reusing mirrored radii; mention it rather than attempting it under pressure.