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:
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
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):
/ \ / \
(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).
Happy Coding 😊
By Programmers Army