Longest Palindromic Substring

Medium#5from the centre outwards

You get a string. Find its longest piece of consecutive characters that reads the same left to right and right to left. Our example: "xabbay" — the answer is "abba".

5 Longest Palindromic SubstringWalkthrough · 1×

Example: "xabbay". From each of the 11 centres — 6 letters and 5 gaps between them — the pointers walk outwards while the letters match.

0x1a2b3b4a5ybests[0 .. 0]x
under a pointerpalindrome around the centrelongest so far

Any single letter is a palindrome: the best so far is s[0 .. 0] = "x"

01/91
restart · back · play · step
Speed
1function longestPalindrome(s):
2 start = 0; end = 0 // best: s[start .. end]
3 for center from 0 to 2 * len(s) - 2:
4 left = floor(center / 2)
5 right = left + center mod 2 // odd: a gap
6 while left >= 0 and right < len(s):
7 if s[left] != s[right]: break
8 left = left - 1; right = right + 1
9 if right - left - 1 > end - start + 1:
10 start = left + 1; end = right - 1
11 return s[start .. end]
state
center
–
left
–
right
–
start
0
end
0
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A palindrome is mirrored around its middle. So start from the middle and step outwards while the two letters at the ends match.
  2. 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.
  3. 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 ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.