mediumCodingConceptMidSenior
You need the longest palindrome in a string. Where does centre-expansion cost you, and what does it cost?
Every palindrome is fixed by its centre, and a string of length n has 2n minus 1 of them once the gaps between characters are counted. Expanding outwards from each is O(n squared) worst case in O(1) extra space, and the worst case is reached by a string of one repeated character, where the expansions from every centre run all the way to the boundary.
6 min readUpdated 2026-08-15
Answer
Short answer
For longest palindromic substring, expand around every character center and every gap between characters. There are 2n - 1 centers, each expansion can cost O(n), so center expansion is O(n squared) worst case and O(1) extra space. The worst case is a string of repeated characters, where most centers expand nearly to the boundary.
Was this answer helpful?
Likely follow-ups
- Return the count of palindromic substrings rather than the longest one. How much of your code survives?
- Why is the dynamic-programming formulation filled by increasing length rather than by row?
- Find the longest palindrome you can build by deleting characters instead of by cutting a window. What problem is that?
- The string is ten million characters and arrives as a stream you cannot rewind. Which approaches are still available?
Related questions
- Detect whether a linked list has a cycle, and return the node where the cycle begins.mediumAlso on two-pointers4 min
- Find the length of the longest substring without repeating characters.mediumAlso on two-pointers2 min
- Remove the nth node from the end of a singly linked list in a single pass.mediumAlso on two-pointers4 min
- Return every distinct triplet in the array that sums to zero.mediumAlso on two-pointers4 min