Given a sequence, find the length of the longest palindromic subsequence in it. For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as “BABCBAB” is the longest palindromic subseuqnce in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.

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. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem and can efficiently solved using Dynamic Programming.

  • Optimal Substructure:

Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0..n-1].

If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Following is a general recursive solution with all cases handled.

// Everay single character is a palindrom 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 
  • Overlapping Subproblems

Following is simple recursive implementation of the LPS problem. The implementation simply follows the recursive structure mentioned above.

[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23include%3Cstring.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20get%20max%20of%20two%20integers%0Aint%20max%20(int%20x%2C%20int%20y)%20%7B%20return%20(x%20%3E%20y)%3F%20x%20%3A%20y%3B%20%7D%0A%20%0A%2F%2F%20Returns%20the%20length%20of%20the%20longest%20palindromic%20subsequence%20in%20seq%0Aint%20lps(char%20*seq%2C%20int%20i%2C%20int%20j)%0A%7B%0A%20%20%20%2F%2F%20Base%20Case%201%3A%20If%20there%20is%20only%201%20character%0A%20%20%20if%20(i%20%3D%3D%20j)%0A%20%20%20%20%20return%201%3B%0A%20%0A%20%20%20%2F%2F%20Base%20Case%202%3A%20If%20there%20are%20only%202%20characters%20and%20both%20are%20same%0A%20%20%20if%20(seq%5Bi%5D%20%3D%3D%20seq%5Bj%5D%20%26%26%20i%20%2B%201%20%3D%3D%20j)%0A%20%20%20%20%20return%202%3B%0A%20%0A%20%20%20%2F%2F%20If%20the%20first%20and%20last%20characters%20match%0A%20%20%20if%20(seq%5Bi%5D%20%3D%3D%20seq%5Bj%5D)%0A%20%20%20%20%20%20return%20lps%20(seq%2C%20i%2B1%2C%20j-1)%20%2B%202%3B%0A%20%0A%20%20%20%2F%2F%20If%20the%20first%20and%20last%20characters%20do%20not%20match%0A%20%20%20return%20max(%20lps(seq%2C%20i%2C%20j-1)%2C%20lps(seq%2C%20i%2B1%2C%20j)%20)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20char%20seq%5B%5D%20%3D%20%22GEEKSFORGEEKS%22%3B%0A%20%20%20%20int%20n%20%3D%20strlen(seq)%3B%0A%20%20%20%20printf%20(%22The%20length%20of%20the%20LPS%20is%20%25d%22%2C%20lps(seq%2C%200%2C%20n-1))%3B%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]

Output:

The length of the LPS is 5

Considering the above implementation, following is a partial recursion tree for a sequence of length 6 with all different characters.

               L(0, 5)
             /        \ 
            /          \  
        L(1,5)          L(0,4)
       /    \            /    \
      /      \          /      \
  L(2,5)    L(1,4)  L(1,4)  L(0,3)

In the above partial recursion tree, L(1, 4) is being solved twice. If we draw the complete recursion tree, then we can see that there are many subproblems which are solved again and again. Since same suproblems are called again, this problem has Overlapping Subprolems property. So LPS problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array L[][] in bottom up manner.

[ad type=”banner”]

Dynamic Programming Solution

[pastacode lang=”java” manual=”%2F%2FA%20Dynamic%20Programming%20based%20Python%20Program%20for%20the%20Egg%20Dropping%20Puzzle%0Aclass%20LPS%0A%7B%0A%20%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20get%20max%20of%20two%20integers%0A%20%20%20%20static%20int%20max%20(int%20x%2C%20int%20y)%20%7B%20return%20(x%20%3E%20y)%3F%20x%20%3A%20y%3B%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Returns%20the%20length%20of%20the%20longest%20palindromic%20subsequence%20in%20seq%0A%20%20%20%20static%20int%20lps(String%20seq)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20int%20n%20%3D%20seq.length()%3B%0A%20%20%20%20%20%20%20int%20i%2C%20j%2C%20cl%3B%0A%20%20%20%20%20%20%20int%20L%5B%5D%5B%5D%20%3D%20new%20int%5Bn%5D%5Bn%5D%3B%20%20%2F%2F%20Create%20a%20table%20to%20store%20results%20of%20subproblems%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%2F%2F%20Strings%20of%20length%201%20are%20palindrome%20of%20lentgh%201%0A%20%20%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20L%5Bi%5D%5Bi%5D%20%3D%201%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Build%20the%20table.%20Note%20that%20the%20lower%20diagonal%20values%20of%20table%20are%0A%20%20%20%20%20%20%20%20%2F%2F%20useless%20and%20not%20filled%20in%20the%20process.%20The%20values%20are%20filled%20in%20a%0A%20%20%20%20%20%20%20%20%2F%2F%20manner%20similar%20to%20Matrix%20Chain%20Multiplication%20DP%20solution%20(See%0A%20%20%20%20%20%20%20%20%2F%2F%20http%3A%2F%2Fwww.geeksforgeeks.org%2Farchives%2F15553).%20cl%20is%20length%20of%0A%20%20%20%20%20%20%20%20%2F%2F%20substring%0A%20%20%20%20%20%20%20%20for%20(cl%3D2%3B%20cl%3C%3Dn%3B%20cl%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3Cn-cl%2B1%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20i%2Bcl-1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(seq.charAt(i)%20%3D%3D%20seq.charAt(j)%20%26%26%20cl%20%3D%3D%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20L%5Bi%5D%5Bj%5D%20%3D%202%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(seq.charAt(i)%20%3D%3D%20seq.charAt(j))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20L%5Bi%5D%5Bj%5D%20%3D%20L%5Bi%2B1%5D%5Bj-1%5D%20%2B%202%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20L%5Bi%5D%5Bj%5D%20%3D%20max(L%5Bi%5D%5Bj-1%5D%2C%20L%5Bi%2B1%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20L%5B0%5D%5Bn-1%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20String%20seq%20%3D%20%22GEEKSFORGEEKS%22%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20seq.length()%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22The%20lnegth%20of%20the%20lps%20is%20%22%2B%20lps(seq))%3B%0A%20%20%20%20%7D%0A%7D” message=”Java” highlight=”” provider=”manual”/]

Output :

The lnegth of the LPS is 7

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

This problem is close to the Longest Common Subsequence (LCS) problem. In fact, we can use LCS as a subroutine to solve this problem. Following is the two step solution that uses LCS.

  • Reverse the given sequence and store the reverse in another array say rev[0..n-1]
  • LCS of the given sequence and rev[] will be the longest palindromic sequence.
    This solution is also a O(n^2) solution.
[ad type=”banner”]