Longest Palindromic Subsequence: Reducing complexity from O(2^N) to O(N^2)


Reading time: 20 minutes | Coding time: 10 minutes

The longest palindrome subsequence problem (LPS) is the problem to find longest subsequences of a string that is also a palindrome. 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 and the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N^2).

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]

algorithm


    // *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*
    Else L(i, j) =  L(i + 1, j - 1) + 2 
C++ implementation of above algorithm:-

    #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.

Let us consider a recursive tree for a sequence of length 6 having all distinct characters whose LPS length is 1.

op

Here, same sub-problems(highlighted in same color) 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)