The problem
A palindrome reads the same forwards and backwards. Given a string s, return its longest substring (a run of consecutive characters) that is a palindrome. If there are several of that length, any one will do.
Examples
- Input
s = "babad"
- Output
"bab"
- Input
s = "cbbd"
- Output
"bb"
Constraints
- 1 ≤ s.length ≤ 1000
- Digits and English letters only.
The idea
Every palindrome has a centre; growing outwards from each of the 2n − 1 centres finds them all, in O(n²). Manacher’s algorithm does it in O(n). First put # between the letters and at both ends — abba becomes #a#b#b#a# — so every palindrome, odd or even, has one character at its centre. p[i] records how far the palindrome centred at i reaches.
Keep the palindrome that reaches furthest right, centred at center, ending at right. For a new centre i inside it, its mirror 2·center − i has already been measured, and the big palindrome guarantees i matches at least min(p[mirror], right − i) — so start there instead of at 0, and only then compare letters. Every comparison that succeeds pushes right further, and right never moves back, so the comparisons total O(n).
- Time
- O(n)
- Space
- O(n) — the reach of each centre
Solution · every language run against every case
class Solution: def longestPalindrome(self, s: str) -> str: # Manacher's algorithm. Put "#" between the letters so every palindrome has a middle: # "abba" becomes "#a#b#b#a#". p[i] is how far the palindrome centred at i reaches. t = "#" + "#".join(s) + "#" n = len(t) p = [0] * n center = right = 0 # the palindrome reaching furthest right so far for i in range(n): if i < right: p[i] = min(right - i, p[2 * center - i]) # its mirror image already knows this much while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]: p[i] += 1 if i + p[i] > right: center, right = i, i + p[i] i = max(range(n), key=lambda k: p[k]) start = (i - p[i]) // 2 # back from "#" positions to positions in s return s[start : start + p[i]]