Problem 35: Longest palindromic substring

def longest_palindrome(s: str) -> str: """ Return the longest palindromic substring of `s`. If there are several with the same maximum length, any one of them is returned. """ n = len(s) if n < 2: return s # Helper to expand around a centre and return the length of the palindrome. def expand(left: int, right: int) -> int: while left >= 0 and right < n and s[left] == s[right]: left -= 1 right += 1 # after the loop left/right are one step beyond the palindrome bounds return right - left - 1 # length of palindrome start = 0 max_len = 1 for i in range(n): # odd length palindrome (single character centre) len1 = expand(i, i) # even length palindrome (centre between i and i+1) len2 = expand(i, i + 1) cur_len = len1 if len1 > len2 else len2 if cur_len > max_len: # update start index based on the current centre # cur_len = right - left - 1 => left = i - (cur_len-1)//2, right = i + cur_len//2 start = i - (cur_len - 1) // 2 max_len = cur_len return s[start:start + max_len]