516. Longest Palindromic Subsequence

Problem Link

Description

---

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.

 

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

Solution

---

Python3

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        N = len(s)
 
        @cache
        def go(i, j):
            if i == j: return 1
            if i > j: return 0
 
            if s[i] == s[j]:
                return 2 + go(i + 1, j - 1)
            
            return max(go(i + 1, j), go(i, j - 1))
        
        return go(0, N - 1)

C++

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> mem(n,vector<int>(n));
        
        return helper(0, n-1, s, mem);
    }
    
    int helper(int start, int end, string &s, vector<vector<int>> &mem){
        if (start == end) return 1;
        if (start > end) return 0 ;
        if (mem[start][end]) return mem[start][end];
        
        return mem[start][end] = s[start] == s[end] ? 2 + helper(start+1, end-1, s, mem) : 
        max(helper(start+1,end,s, mem), helper(start, end -1,s, mem));
    }
};