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.