Longest Palindromic Subsequence

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

Example

#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