Longest Palindromic Substring
WHAT IT SAYS
Find the longest substring that reads the same forwards and backwards.
WHAT IT'S REALLY ASKING
"Every palindrome grows outward from a middle — a character, or the seam between two equal characters. There are only 2n-1 possible middles in a string, but there are n^2/2 substrings. Which of those two sets would you rather search?"
Check every substring
O(n^3) time, O(1) spaceEnumerate all O(n^2) substrings and test each one for palindromicity by walking two pointers inward from its ends.
WHERE THE WORK IS WASTED — The check for s[i..j] compares the outer pair, then walks inward and re-verifies the exact interior that you already verified when you checked s[i+1..j-1] — a substring you also enumerated, independently, and threw away. Every core gets re-examined once for every pair of characters that happens to wrap it. The fact 'the middle is a palindrome' is recomputed from scratch, over and over, when it is the one thing you already knew.
Every palindrome has a centre, and centres are scarce.
The recursive definition is the whole story: s[i..j] is a palindrome exactly when s[i] equals s[j] AND the interior s[i+1..j-1] is a palindrome. Unroll that all the way down and you always land on a base case — a single character, or an empty seam between two characters. Run it backwards. Every palindrome is GENERATED by starting at one of those base cases and repeatedly adding a matching pair of characters, one on each side. And every palindrome HAS such a base case: its middle character if its length is odd, its middle seam if its length is even. The correspondence is exact — centres and radii on one side, palindromes on the other, nothing missing and nothing invented. So count the centres. There are n single characters and n-1 seams: 2n-1 in total. Linear. Against n(n+1)/2 substrings. You have swapped a quadratic search space for a linear one, and you did not lose a single candidate. One more property makes the growth cheap. When the mirrored characters at a given radius fail to match, no LARGER palindrome around that same centre can exist either — a bigger one would have to contain this exact failing pair. The failure is permanent, not temporary. So growth around a centre is monotone: extend while it matches, stop dead when it does not, and never come back. That is why the total work is O(n^2) and yet no comparison is ever wasted: you only ever extend palindromes you have already proven, and you never test a candidate whose interior you have not already verified.
Grow outward from every centre
O(n^2) time worst case (a string of identical characters expands fully at every centre), O(1) extra spaceFor each of the 2n-1 centres — n single characters and n-1 seams — push two pointers outward while the mirrored characters match and both stay in bounds. Track the longest span you ever reach. No table, no recursion.
Manacher's, for the O(n)
O(n) time, O(n) spaceThe linear algorithm exists, and its idea is a refinement of this same one: if you already know a big palindrome, then the palindrome radius at any position inside it is at least the radius at its mirror image on the other side — a free lower bound that means you never restart a centre's expansion from zero. Worth knowing, rarely the point of the interview, and worthless if you cannot explain why the mirror bound holds.
Enumerate the Centres, Not the Candidates
YOU'LL SEE IT AGAIN WHEN
- The objects you want are defined recursively as 'a smaller object of the same kind, wrapped in one more layer' — palindromes, nested pairs, symmetric structures.
- The number of possible seeds (centres, roots, starting points) is linear while the number of candidate objects is quadratic.
- A failed check at one size is permanent for that seed — growing cannot repair it — so expansion is monotone and can stop the instant it fails.