516. Longest Palindromic Subsequence

Problem Statement

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.

Intuition

Appraoahc:

We reverse the string and find the LCS, Intuition
When we reverse the string, The palindromes will remain same

in reverse as well as og
but all other changes

eg-> abad
     daba
We can find aba

Links

https://leetcode.com/problems/longest-palindromic-subsequence/

Video Links

Approach 1:

C++

class Solution {
public:
    int lcs(string &s1, string &s2, int i, int j, vector<vector<int>> &dp){
        if( i<0 or j<0)
            return 0;

        if(dp[i][j] != -1)
            return dp[i][j];

        if(s1[i] == s2[j])
            return dp[i][j] = 1 + lcs(s1, s2, i-1, j-1, dp);

        return dp[i][j] = max( lcs(s1, s2, i-1, j, dp), lcs(s1, s2, i, j-1, dp) );
    }

    int longestPalindromeSubseq(string s) {
        string s2 = s; 
        reverse(s2.begin(), s2.end());
        int i = s.size()-1;
        vector<vector<int>> dp(i+1, vector<int>(i+1, -1));

        return lcs(s, s2, i, i, dp);
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++