1682. Longest Palindromic Subsequence II (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        result = 0
        dp = [(0, "")] * n
        for step in range(1, n):
            for i in range(n - step):
                (a1, b1), (a2, b2) = dp[i], dp[i + 1]
                if s[i] == s[i + step]:
                    if s[i] == b2:
                        dp[i] = dp[i + 1]
                    else:
                        dp[i] = (a2 + 2, s[i])
                        result = max(result, dp[i][0])
                else:
                    a = max(a1, a2)
                    b = ""
                    if a1 == a2:
                        if b1 != b2:
                            b = "#"
                        else:
                            b = b1
                    elif a1 > a2:
                        b = b1
                    else:
                        b = b2
                    dp[i] = (a, b)
        return result