Longest Palindromic Subsequence (With Solution)

Longest Palindromic Subsequence

Problem Statement

Given a string S, find the common palindromic sequence ( A sequence that does not need to be contiguous and is a palindrome), which is common in itself.

You need to return the length of the longest palindromic subsequence in A.

A string is said to be palindrome if the reverse of the string is the same as the string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

Examples:

Input: S = “BEBEEED”
Output: 4
Explanation:

The longest common palindromic subsequence is “EEEE”, which has a length of 4

Input: S = “AABCDEBAZ”
Output: 5

LPS Example

Brute force: Recursion Approach

A simple approach to solve this problem is to generate all the subsequences of the given string and find the longest palindromic string among all the generated strings. There are a total of 2^N strings possible, where N denotes the length of the given string.

The idea is to check and compare the first and last characters of the string. There are only two possibilities for the same:

  • If the first and the last characters are the same, it can be ensured that both the characters can be considered in the final palindrome and hence, add 2 to the result, since we have found a sequence of length 2 and recurse the remaining substring S[i + 1, j – 1].
  • In case, the first and the last characters aren’t the same, the following operation must be performed:
    • Recurse S[i + 1, j]
    • Recurse S[ i, j  – 1]
  • Find the maximum length obtained amongst them.

The recursion tree can be shown as follows: LPS(1, N) denotes the length of the longest palindromic subsequence of the given string S[1..N].

LPS Brute force Approach
LPS Brute force Approach

C++ Implementation

int LPS(string S, int left, int right){
        if (left > right) {
            return 0;
        } 
        if(left == right){
            return 1;
        }   
        if (S[left] == S[right])
        {
            return 2 + LPS(str,left+1,right-1);
        }
  
  
     return max(LPS(S, left, right - 1), LPS(S, left + 1, right));
    }

Java Implementation

 static int LPS(String S, int left, int right){
        if (left > right) {
            return 0;
        } 
        if(left == right){
            return 1;
        }   
        if (S.charAt(left) == S.charAt(right) )
        {
            return 2 + LPS(str,left+1,right-1);
        }
  
  
     return Math.max(LPS(S, left, right - 1), LPS(S, left + 1, right));
    }

Python Implementation

def LPS(S, left, right){
        if left > right:
            return 0
        If left == right:
            return 1
        
        if S[left] == S[right]:
            return 2 + LPS(str,left+1,right-1);
  
  
       return max(LPS(S, left, right - 1), LPS(S, left + 1, right))

Time Complexity: O(2^N) where N is the size of the string S.
Space Complexity: O(1), as no extra space is used.


Efficient Approach (Using Dynamic Programming)

The efficient approach uses a dynamic programming approach for the problem.


It can be clearly observed that some of the subsequences are repeating i.e it contains overlapping subproblems. Let us take the example of the string ABCDE.

LPS DP Approach
LPS DP Approach

The subproblems BCD is repeating twice, hence instead of calculating the value twice, we can instead store it in a table. Let’s illustrate the algorithm with the string – “axbdba”.

Consider a dp array of size N * N.

Algorithm:

Fill the table with a start case, dp[i, i] == 1, since all single char in a string is a palindrome, which length is 1.

LPS DP Step 1

When s[i] == s[j]

LPS DP S2

When s[i] == s[j]

LPS DP S3

Continue the process until the whole dp array is filled.

LPS DP S4

Return dp[0][N  – 1] is the longest palindromic subsequence(LPS)

C++ Code for DP Approach

public int LPS(string S) {
        int dp[S.length()][S.length()];
        
        for (int i = S.length() - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < S.length(); j++) {
                if (S[i] == S[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][S.length()-1];
 }

Java Code for DP Approach

public int LPS(String S) {
        int[][] dp = new int[S.length()][S.length()];
        
        for (int i = S.length() - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < S.length(); j++) {
                if (S.charAt(i) == S.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][S.length()-1];
 }

Python Code for DP Approach

def LPS(S):
        dp = [[0 for x in range(len(S))] for x in range(len(S))]
        
        for i in range(len(S) - 1, -1, -1):
            dp[i][i] = 1;
            for j in range(i + 1, len(S)):
                if S[i] == S[j]:
                    dp[i][j] = dp[i+1][j-1] + 2;
                 
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                
            
        return dp[0][S.length()-1];

Time Complexity: O(N^2) where N is the size of the string S.
Space Complexity: O(N^2), as extra dp array is used.


Practice Question

Longest Palindromic Subsequence


Frequently Asked Questions

How to find the longest palindromic subsequence?
The LPS can be calculated efficiently using the dynamic programming approach, which can be solved in O(N^2), where N is the size of the given string.

How to find the palindromic subsequence from the table?
To find the subsequence, which gives us the longest LPS, backtrack from dp[0][N – 1] and trace the path back to dp[0][0].

Previous Post
Number Of Pairs Efficient Approach

Number of Pairs

Next Post
Median Of Two Sorted Arrays

Median of Two Sorted Arrays

Crack your next tech interview with confidence!
Take a free mock interview, get instant⚡️ feedback and recommendation💡
Take Free Mock Interview
Total
0
Share