Why it works
- A palindrome is mirrored around its middle. So start from the middle and step outwards while the two letters at the ends match.
- The middle is a letter when the length is odd ("aba") and the gap between two letters when it is even ("abba"). A string of n letters has n letters and n − 1 gaps: 2n − 1 centres. Trying every one of them misses no palindrome.
- Growing stops at the first pair that differs: any longer piece around this centre holds that pair too, so it is not a palindrome either.
Complexity
Time O(n²): 2n − 1 centres, and from each the pointers take at most n / 2 steps. Memory O(1) besides the answer itself: only start and end are kept, and the piece is cut out once at the end. Manacher’s algorithm finds it in O(n), but interviews rarely expect it.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗