Longest Palindromic Substring
Picture
In abac, aba expands around b. Even palindromes center between characters.
Predict
Does the mirrored radius always copy completely?
Walk through the small example
No, clip at the known boundary. Palindrome symmetry and a rightmost verified boundary reuse earlier expansion work.
Mental model and complete Python solution
Imagine overlapping bubbles around centers. Inside the farthest-reaching bubble, a mirrored center already has a known radius—unless that radius crosses the current bubble wall.
What the function promises: Return one longest palindromic substring. Ties return the earliest encountered center’s result.
def longest_palindrome(text):
transformed = "^#" + "#".join(text) + "#$"
radius = [0] * len(transformed)
center = right = 0
best_center = best_radius = 0
for i in range(1, len(transformed)-1):
mirror = 2*center-i
if i < right:
radius[i] = min(right-i, radius[mirror])
while transformed[i+1+radius[i]] == transformed[i-1-radius[i]]:
radius[i] += 1
if i+radius[i] > right:
center, right = i, i+radius[i]
if radius[i] > best_radius:
best_center, best_radius = i, radius[i]
start = (best_center-best_radius)//2
return text[start:start+best_radius]
assert longest_palindrome("babad") in ("bab","aba")
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("") == ""Work and storage: O(n) time and O(n) space.
When to recognize it: Palindrome symmetry and a rightmost verified boundary reuse earlier expansion work.
Check before applying it: Transformed indices require careful conversion, and the algorithm solves contiguous palindromes, not subsequences.
Change one rule
Need the longest palindromic subsequence.
See what changes
Use interval DP; characters may be skipped, so center expansion is not enough.
Connect
Z algorithm: match every suffix start: Both reuse information inside a rightmost verified interval.
string dp: A palindrome substring is contiguous; LCS permits skips.