Longest Palindromic Substring

Intuition

Basically a DP problem. if s[i:j] is a palindrome, then s[i + 1:j - 1] must be a palindrome.

One tip here is to use 'a a c' to replace 'aac', so that for 'aa' could be treated as 'a a' with odd length.

Solution


class Solution:
    def longestPalindrome(self, s: str) -> str:
        alt = [' ']
        for c in s:
            alt.append(c)
            alt.append(' ')
        lo, hi = 0, 1

        for mid in range(len(alt)):
            i = mid
            j = mid
            while i >= 0 and j < len(alt) and alt[i] == alt[j]:
                i -= 1
                j += 1
            if j - i > hi - lo:
                lo, hi = i, j
        return s[lo // 2 + 1:hi // 2]