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