Longest Palindromic Subsequence

The Longest Palindromic Subsequence or LPS is a very important problem in computer science. In this, we need to find the length of the longest subsequence that is also a palindrome. This problem is different from the longest common substring problem as subsequences are not required to occupy only consecutive positions.

For example, consider the string “bbbab”. The longest palindromic subsequence is “bbbb”. The length of the LPS is 4. 

The naïve solution of this problem is to generate all the possible subsequences of a string and then check if it is a palindrome. This solution will take O(2n) just to generate all the possible subsequences. We are going to first use recursive in this problem. 

The idea is similar to the longest common subsequence problem. We are going to compare the first and last character of the string S[i..j]. There are two possible cases:

  1. If the first and the last character of the string are the same, then we can include them. After that, we need to recur for the remaining substring which is S[i+1,j-1].
  2. If the first and the last character of the string are different, then we will have two separate choices. We can either remove the first character or the last character. If we are removing the first character, then we need to find the result of S[i+1,j]. Similarly, if we are removing the last character, then we need to find the result of S[i,j-1]. Thus, we will return the maximum of these two values. 

We can use this recursive relation for solving this problem:

LPS [i…i] =1

if(S[i] == S[j])

      LPS[i…j] = LPS[i+1…j-1] + 2

else

      LPS[i…j] = max(LPS[i…j-1],LPS[i+1…j])

 

You can check the code below.



 

 

O/P: The length of the LPS is 4

 

The time complexity of this solution is going to be (2n) or exponential and the auxiliary space used by this solution is O(1). This solution is going to compute the same subproblems multiple times. The LPS problem has both overlapping problems and optimal substructure. You can check the below recursion tree of LPS(0,3) for a string whose LPS length is only 1(worst case):

 

                             (0,3)                                          

                             /      \                                             

                        (1,3)     (0,2)                              

                        /     \     /     \                                

                  (2,3)  (1,2) (1,2)  (0,1)             

This problem has both optimal substructure and overlapping sub-problems. Thus, we can use Dynamic Programming for solving this problem. We will store the result of subproblems in a table rather than computing them again and again. You can check the code below:



 

// O/P: The length of the LPS is 4

 

The time and space complexity of this solution is O(n2). You can also use this idea for solving problems like the longest common subsequence and longest palindromic substring.

Exercise: Try to reduce the auxiliary space used to O(n).

Practice Problems:

Happy Coding 😊

By Programmers Army