Problem. Given a string s, return one longest palindromic substring.
This is the classic center-expansion search pattern.
Examples:
s = "babad"→"bab"or"aba"s = "cbbd"→"bb"s = "a"→"a"
Solution. Every palindrome is centered on either one character or the gap between two characters. Expand around each possible center and keep the longest span found.
def longest_palindrome(s):
if len(s) < 2:
return s
best_start = 0
best_end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
for center in range(len(s)):
for left, right in (expand(center, center), expand(center, center + 1)):
if right - left > best_end - best_start:
best_start, best_end = left, right
return s[best_start:best_end + 1]
O(n^2) time, O(1) space.
Gotchas.
- There are both odd-length and even-length centers.
- The problem asks for a substring, not a subsequence.
- Multiple longest answers can exist; returning any one of them is fine unless stated otherwise.