DAY 20 - Longest Palindromic Subsequence

Hey Guys! Nayan here and we are on the day 20th of 100-DAYS Challenge and we have completed 1/5th of the journey with this article. Thanks to this I have undoubtedly been more consistent in my practice and would recommend this to all of you as well.

Let's get started with the problems. To solve this problem we must first understand how to solve a subpart of this problem, which I have already explained on DAY-18 of this series, so if you have not read that, I would please request you to go and understand that article.

Problem 1: Longest Palindromic Subsequence

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.

Examples:

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

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

Intuition:

To solve this problem let's break down the question.
We need to get the subsequence of a string such that the found subsequnce is a palindrome.

What is a palindrome?

A palindrome is a string of characters such that if we reverse the string , there is no change in it.
Example:
"aabaa"or my name "nayan" in this case as well XD.

What is a subsequence?
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Well now that we know the basics, we know the tasks at hand.

Approach: Naive Approach / Brute force

The naive approach would be to generate all the subsequences using recursion.
Then we check if they are a palindrome.
Then we return the max of all subsequences that satisfy this.

It will take exponential time complexity and hence also the reason we won't be taking this approach.

Approach: Optimal + Observation

• Let's revisit the code of longest common subsequence of two strings.
• It allowed us to find the longest common subsequence of two strings in an optimal manner.
• The largest palindrome that a string will have is that string itself reversed.
• None of it's subsequnces will match that length.
• The length of the palindromic subsequence will also remain the same when the entire string is reversed.
• Hence from the above observation we can conclude that the longest palindromic subsequnce will be given by LCS of the same string reversed.
• So our final approach is:
• Reverse the string s.
• Copy the original string s in a temporary string.
• Find the lcs and return it.

Code:

#include <string>
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int ind1 = text1.size();
        int ind2 = text2.size();
        vector<vector<int>> dp(ind1+1, vector<int>(ind2+1,0));

        for(int i = 1; i <=ind1; i++){
            for(int d = 1; d <=ind2; d++){
                if(text1[i-1] == text2[d-1])
                dp[i][d] = 1 + dp[i-1][d-1];
                else
                dp[i][d] = max(dp[i-1][d], dp[i][d-1]);
                }
            }
        return dp[ind1][ind2];
        }

    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(s.begin(), s.end());
        if(s.size() < 2 || s == t){
            return s.size();
        }
        return longestCommonSubsequence(s,t);

    }
};

Complexity Analysis:

Time Complexity: O(N^2) + O(N)
Space Complexity: O(N^2) where N and M are sizes of strings.

Hence we solved the problem in the most optimal way possible.

We can space optimize the LCS further as we did previously.