Given a sequence, find the length of the longest palindromic subsequence in it.
Answers
Answer:here your answer
Step-by-step explanation:
Longest Palindromic Subsequence is the subsequence of a given sequence, and the subsequence is a palindrome.
In this problem, one sequence of characters is given, we have to find the longest length of a palindromic subsequence.
To solve this problem, we can use the recursive formula,
If L (0, n-1) is used to store a length of longest palindromic subsequence, then
L (0, n-1) := L (1, n-2) + 2 (When 0'th and (n-1)'th characters are same).
Input and Output
Input:
A string with different letters or symbols. Say the input is “ABCDEEAB”
Output:
The longest length of the largest palindromic subsequence. Here it is 4.
ABCDEEAB. So the palindrome is AEEA.
Algorithm
palSubSeqLen(str)
Input: The given string.
Output: Length of longest palindromic subsequence.
Begin
n = length of the string
create a table called lenTable of size n x n and fill with 1s
for col := 2 to n, do
for i := 0 to n – col, do
j := i + col – 1
if str[i] = str[j] and col = 2, then
lenTable[i, j] := 2
else if str[i] = str[j], then
lenTable[i, j] := lenTable[i+1, j-1] + 2
else
lenTable[i, j] := maximum of lenTable[i, j-1] and lenTable[i+1, j]
done
done
return lenTable[0, n-1]
End
Source Code (C++)
#include<iostream>
using namespace std;
int max (int x, int y) {
return (x > y)? x : y;
}
int palSubseqLen(string str) {
int n = str.size();
int lenTable[n][n]; // Create a table to store results of subproblems
for (int i = 0; i < n; i++)
lenTable[i][i] = 1; //when string length is 1, it is palindrome
for (int col=2; col<=n; col++) {
for (int i=0; i<n-col+1; i++) {
int j = i+col-1;
if (str[i] == str[j] && col == 2)
lenTable[i][j] = 2;
else if (str[i] == str[j])
lenTable[i][j] = lenTable[i+1][j-1] + 2;
else
lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
}
}
return lenTable[0][n-1];
}
int main() {
string sequence = "ABCDEEAB";
int n = sequence.size();
cout << "The length of the longest palindrome subsequence is: " << palSubseqLen(sequence);
}
Output
The length of the longest palindrome subsequence is: 4