Longest Palindromic Subsequence is essentially LCS

516. Longest Palindromic Subsequence

This is April 13, 2023’s daily problem. It is a quite interesting problem as the LPS is essentially LCS. We can change this problem to longest common sequence. And it can be explained by using the following example

a, b, c, e, c, b, f, a

Essentialy is looking for the common sequence of:

[a, b, c] and reversed [c, b, f, a]

which is

the common sequence of

[a, b, c] and [a, f, b, c].

We can use the transition rule of LCS:

if s[i] == s[j]:
LCS(i, j) = 1 + LCS(i - 1, j - 1)
else:
LCS(i, j) = max(LCS(i, j - 1) , LCS(i - 1, j))

Complexity

• Time complexity: O(n²)
• Space complexity: O(n²) for the memo.

Code

class Solution {
public:
string s;
int n;
    int lcs(vector<vector<int>>& memo, int i, int j){
        if (memo[i][j] != -1) return memo[i][j];
        if (i == 0 || j == n + 1) return memo[i][j] = 0;
        if (s[i-1] == s[j-1]){
            return memo[i][j] = 1 + lcs(memo, i - 1, j + 1);
        } else {
            return memo[i][j] = max(lcs(memo, i - 1, j), lcs(memo, i, j + 1));
        }

    }
    int longestPalindromeSubseq(string s) {
        this->s = s;
        this-> n= s.size();
         vector<vector<int>>memo(n + 2, vector<int>(n+2, -1));
         int ret = 0;
         for (int i =1; i <= n; ++i){
             ret = max(ret,1 +  2*lcs(memo, i - 1, i + 1));
             ret = max(ret, 2*lcs(memo, i - 1, i));
         }
         return ret;
        
    }
};

Thanks for reading and hope it is helpful.