Run it: Longest palindromic substring in code
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
Each palindrome has a centre. There are 2n−1 doable 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" fully, 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 other
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. This reaches 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. This 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 also 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. Spotting 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; trying 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, data from before 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 each palindrome becomes odd-length. It reaches 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 reaches 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 trying 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 each 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. This 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). This is an unexpected and elegant connection.