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.

Expected Output: 9
Explanation: The longest palindromic subsequence is “MALAYALAM” of length 9.


  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++){
				dp[i][j] = dp[i-1][j-1]+1;
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
	return dp[m][n];

int main(){
	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.


Leave a Reply

Your email address will not be published.