Longest Palindromic Subsequence

Problem Id: 516 Difficulty: Medium


Intuition

Solution


class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        length = 2
        while length <= n:
            for lo in range(n - length + 1):
                hi = lo + length - 1
                if s[lo] == s[hi]:
                    dp[lo][hi] = dp[lo+1][hi-1] + 2
                else:
                    dp[lo][hi] = max(dp[lo + 1][hi], dp[lo][hi - 1])
            length += 1
        return dp[0][n - 1]