Problem description:

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: “bbbab”
Output: 4
One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input: “cbbd”
Output: 2
One possible longest palindromic subsequence is “bb”.

Solution1 DFS:

Use a 2D array and two pointers to check longest palindromic subsequence. memo[i][j] means the longest palindromic subsequence on between i and j.

example:

1
2
b b b a b
  i     j

if s[i] == s[j], the length would increase 2.
memo[start][end]= helper(s, start+1, end-1, memo)+2;

1
2
b b b a b
  i   j

if s[i]!= s[j], the length should be max(memo[i+1][j], memo[i][j-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n= s.length();
        vector<vector<int>> memo(n, vector<int>(n, -1));
        return helper(s, 0, n-1, memo);
    }
    
    int helper(string &s, int start, int end, vector<vector<int>>& memo){
        if(memo[start][end] != -1) return memo[start][end];
        if(start> end) return 0;
        if(start == end) return 1;
        
        if(s[start] == s[end])
            memo[start][end]= helper(s, start+1, end-1, memo)+2;
        else
            memo[start][end]= max(helper(s, start+1, end, memo), helper(s, start, end-1, memo));
        
        return memo[start][end];
    }
};

Solution2 DP:

Similar to previous idea. Use a pointer i to denote the length that we traverse right now. Another pointer j to denote check the palindromic substring.

example:

1
2
b b b a b
  j i

dp[i][j]= dp[i-1][j+1]+2 

1
2
b b b a b
  j   i

dp[i][j]= max(dp[i-1][j], dp[i][j+1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # 2D dp
        # traverse the string, another pointer expand from index i to 0
        # notice for each dp[i][i] initiate to 1 because a character is its own palindromic 
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
            for j in range(i-1, -1, -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[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));
        for(int i= 0; i< s.length(); i++){
            dp[i][i]= 1;
            for(int j= i-1; j>= 0; j--){
                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[s.length()-1][0];
    }
};

reference: