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:**

- The problem is similar to finding the length of longest common subsequence for two strings. And can be solved using dynamic programming.
- 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.**

## 3 comments