Learning On the Way

516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

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 
     
    for L in range(2, N + 1): 
        for i in range(N - L + 1): 
            j = i + L - 1 
            if s[i] == s[j]: 
                dp[i][j] = dp[i + 1][j - 1] +2 
            else: 
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 
                 
    return dp[0][-1]