Longest Palindromic Subsequence — 2D DP

Problem

Return the length of the longest palindromic subsequence (not contiguous).

Example: "bbbab" → 4 ("bbbb")

Approach — 2D DP (diagonal fill)

dp[i][j] = longest palindromic subsequence in s[i..j].

dp[i][i] = 1
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])

Time: O(n²) | Space: O(n²), optimizable to O(n)

Solutions

Python

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
        for length in range(2,n+1):
            for i in range(n-length+1):
                j=i+length-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][n-1]

C++

class Solution {
public:
    int longestPalindromeSubseq(string s){
        int n=s.size(); vector<vector<int>> dp(n,vector<int>(n,0));
        for(int i=0;i<n;i++) dp[i][i]=1;
        for(int len=2;len<=n;len++)
            for(int i=0;i<=n-len;i++){
                int j=i+len-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][n-1];
    }
};

Complexity

Time: O(n²) | Space: O(n²)