Reading time: 20 minutes | Coding time: 10 minutes

The longest palindrome subsequence problem (LPS) is the problem to find the length of longest subsequence in a string that is a palindrome. This can be done using Dynamic Programming in O(N²) time.

Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. We will see two solutions:

• one which is a naive solution
• the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N²).

For example:

Sequence:- ABBDCACB
The length of longest palindromic subsequence is 5.
The longest palindromic subsequence is BCACB.

Sequence:- BBABCBCAB
The length of longest palindromic subsequence is 7.
The longest palindromic subsequence is BABCBAB.

The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence. This solution is exponential in term of time complexity.

Naive approach using Recursive method

Here, we can use Recursive method to solve this problem.

The idea is to compare the last and first character of the string. There are two possibilities:

1. If last and first character of string is same, we can include both characters in palindrome and recurse for remaining substring X[i+1 , j-1]

2. If last character of string is different from the first character, we return maximum of the two values we get by:

• removing the last character and recursing for the remaining substring X[i, j-1]
• removing the first character and recursing for the remaining substring X[i+1, j]

Brute force algorithm (recursion)

• Every single character is a palindrome of length 1

L(i, i) = 1 for all indexes i in given sequence

• IF first and last characters are not same

If (X[i] != X[j]) L(i, j) = max{L(i + 1, j),L(i, j - 1)}

• If there are only 2 characters and both are same*

Else if (j == i + 1) L(i, j) = 2

If there are more than two characters, and first and last characters are same.

C++ implementation of above brute force approach:

    #include<iostream>
    using namespace std;
    // A utility function to get max of two integers 
    int max (int x, int y) { return (x > y)? x : y; } 
    // Returns the length of the longest palindromic subsequence in seq 
    int longestpalindrome(char *seq, int i, int j) 
    {     
    // Base Case 1: If there is only 1 character 
     if (i == j) 
      return 1; 
    // *Base Case 2: If there are only 2  
    // characters and both are same* 
    if (seq[i] == seq[j] && i + 1 == j) 
    return 2; 
     // If the first and last characters match 
    if (seq[i] == seq[j]) 
    return longestpalindrome(seq, i+1, j-1) + 2; 
    // If the first and last characters do not match 
    return max( longestpalindrome(seq, i, j-1), longestpalindrome(seq, i+1, j) ); 
}   
/* Driver program to test above functions */
int main() 
{
 
    char seq[] = "ABBDCACB"; 
    int n = strlen(seq); 
    cout << "The length of the longest palindrome subsequence is " 
         << longestpalindrome(seq, 0, n-1); 
    return 0; 

} 

OUTPUT:-

The length of the longest palindrome subsequence is 5.

The worst case time complexity of above solution is exponential O(2^n) and auxiliary space used by the program is O(1).

The worst case happens when there is no repeated character present in X and each recursive call will end up in two recursive calls.

Dynamic programming approach

The LPS problem has an optimal substructure and also exhibits overlapping subproblems.

The idea is as follows:

L[i][j] = length of the longest palindromic subtring 
          in substring from index i to j

Base case is:

L[i][i] = 1

as if there is only one character, then the longest palindromic substring has length 1 as there is only one option.

L[i][j] = 2    if char[i] == char[j] and j-i = 1

as there are two same characters, then there is one palindrome of length 2 hence, it is the length of the longest palindromic substring.

The relations to compute the DP table are as follows:

If the ith and jth characters are same, then the longest palindromic subsequence in L[i][j] is same as L[i+1][j-1] + 2. This is because L[i+1][j-1] is for the substring where the ith and jth characters are removed from L[i][j].

L[i][j] = L[i+1][j-1] + 2;

The other case is that L[i][j] will be the maximum of either of the substring where ith character or jth character is removed.

L[i][j] = max(L[i][j-1], L[i+1][j]);

With this, our answer will be contained in:

L[0][N-1] where N is the length of the original string

Same sub-problems are getting computed again and again.

As we can see LPS has optimal substructure and overlapping subproblems, it can be solved by Dynamic programming, where values can be Memoised or Tabulated rather than computing it again and again.

Using Dynamic Programming:

     #include<iostream>
     using namespace std;
    int max (int x, int y) { return (x > y)? x : y; } 
    // Returns the length of the longest palindromic subsequence in seq 
    int longestpalindrome(char *str) 
    {
     int n = strlen(str); 
     int i, j, cl; 
     int L[n][n];  // Create a table to store results of subproblems 
     // Strings of length 1 are palindrome of lentgh 1 
     for (i = 0; i < n; i++) 
      L[i][i] = 1; 
     // Build the table. Note that the lower diagonal values of table are 
     // useless and not filled in the process. The values are filled in a 
     // manner similar to Matrix Chain Multiplication DP solution
    for (cl=2; cl <= n; cl++) 
    { 
        for (i=0; i < n-cl+1; i++) 
        { 
            j = i+cl-1; 
            if (str[i] == str[j] && cl == 2) 
               L[i][j] = 2; 
            else if (str[i] == str[j]) 
               L[i][j] = L[i+1][j-1] + 2; 
            else
               L[i][j] = max(L[i][j-1], L[i+1][j]); 
        } 
    } 
  
    return L[0][n-1]; 
} 
/* *Driver program to test above functions* */
int main() 
{

    char arr[] = "ABBDCACB"; 
    int n = strlen(arr); 
    cout << "The length of the Longest Palindrome Subsequence is " <<       longestpalindrome(arr)); 
    getchar(); 
    return 0; 

} 

OUTPUT:-

The length of the Longest Palindrome Subsequence is 5.

NOTE:- Time Complexity of the above implementation is O(n^2) which is much better than the worst case time complexity of Naive Recursive implementation.

We reduced the time complexity from O(2^N) to O(N^2)