5. Longest Palindromic Substring

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        def expand(l, r):
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # When the loop stops, l and r are one step beyond the valid palindrome!
            return l + 1, r
        best_start, best_end = 0, 1
        for i in range(n):
            # odd-length centering at i
            l1, r1 = expand(i, i)
            if r1 - l1 > best_end - best_start:
                best_start, best_end = l1, r1
            l2, r2 = expand(i, i+1)
            if r2 - l2 > best_end - best_start:
                best_start, best_end = l2, r2
        return s[best_start:best_end]
            


        # result = ''
        # def expand(s, left, right):
        #     while left >= 0 and right < len(s) and s[left] == s[right]:
        #         left -= 1
        #         right += 1
        #     return s[left+1:right]

        # for i in range(len(s)):
        #     # odd
        #     tmp = expand(s, i, i)
        #     if len(tmp) > len(result):
        #         result = tmp
        #     # even
        #     tmp = expand(s, i, i+1)
        #     if len(tmp) > len(result):
        #         result = tmp
        # return result