Longest Palindromic Subsequence (DP-05)

You are given a string X of length m. You need to find the length of the longest subsequence of X which is palindrome.
A subsequence is a sequence that can be derived from a sequence by deleting some characters without changing the order of the characters.
A palindrome is a word which spells the same from left to right and right to left. Eg: MALAYALAM.

Sample Input: X = “YJKMALAUITYALAMMPOT”
Expected Output: 9
Explanation: The longest palindromic subsequence is “MALAYALAM” of length 9.

Algorithm:

1. The problem is similar to finding the length of longest common subsequence for two strings. And can be solved using dynamic programming.
2. Here, create a new string which is the reverse of the original string. Then find the length of the longest common subsequence for the two strings.
/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

int helper(string X, string Y, int m, int n){
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(X[i-1]==Y[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}

int main(){

string X = "YJKMALAUITYALAMMPOT";
string Y = X;
reverse(Y.begin(), Y.end());
cout<<helper(X, Y, X.size(), X.size());
return 0;
}

Also take a look at another popular interview question Longest Common Subsequence.