Description
Return a longest contiguous palindrome in a nonempty string. Any longest answer is acceptable.
Solution
def longest_palindrome(s):
start = 0
size = 1
for center in range(len(s)):
for left,right in ((center,center),(center,center+1)):
while left >= 0 and right < len(s) and s[left] == s[right]:
if right-left+1 > size:
start,size = left,right-left+1
left -= 1
right += 1
return s[start:start+size]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["cabbad"]- Output
"abba"
abba is a palindrome of length four.
Example 2
- Input
["abc"]- Output
"a"
Every single letter ties; this solution retains a.
Example 3
- Input
["z"]- Output
"z"
The single character is a palindrome.
Approach
Expand around each character and each gap, recording the longest matching interval.
Time & space
O(n²) time; O(1) auxiliary space excluding the returned substring. Here n is the input length.