Longest Palindromic Subsequence

Nishant Rana
Last Updated: May 13, 2022

Introduction:

We are given a String, and we need to find the length of the Longest Palindromic Subsequence.

 

Let us see few examples:

 

Input: 

“ZXYFYKXAC”

 

Output: 5

 

Explanation: 

“XYFYX” is the longest palindromic subsequence of length 5.

 

Input: 

“ABBBBA”

 

Output: 6

 

Explanation: 

“ABBBBA” is the longest palindromic subsequence of length 6.

 

APPROACH 1:

We can use recursion to solve this question. We will keep two pointers, ‘i’ and ‘j’. The ‘i’ pointer will initially point at 0, and the ‘j’ pointer will initially point at ‘str.length()-1’. At any recursive call, if the character at ‘i’ and ‘j’ positions are the same, we will call our recursive function with the values ‘ i - 1’ and ‘j - 1’ and add 1 to the answer returned by this recursive call as we met a case for a string to be a palindrome.

In the else part, when the characters at the ‘i’ and ‘j’ positions are not the same, we will make two recursive calls with (i, j-1) and (i-1, j) because the elements at ith and jth position are not contributing into a palindromic sequence, and return the maximum among both of them.

Refer to the below implementation for the above approach.

 

class Main {
 
    // A utility function to find the max of two given integers.
    static int max(int x, int y) {
        return (x > y) ? x : y;
    }
    
    // Returns the longest palindromic subsequence in the arr array
    static int lps(char arr[], int i, int j) {
        
        // Base Case 1: If only 1 character present
        if (i == j) {
            return 1;
        }
 
        // Base Case 2: If only 2 characters are present and both same
        if (arr[i] == arr[j] && i + 1 == j) {
            return 2;
        }
 
        // If first and the last character matches
        if (arr[i] == arr[j]) {
            return lps(arr, i + 1, j - 1) + 2;
        }
 
        // If first and the last characters does not match
        return max(lps(arr, i, j - 1), lps(arr, i + 1, j));
    }
 
 
    public static void main(String[] args) {
        String seq = "ZXYFYKXAC";
        int n = seq.length();

        System.out.printf("The length of the Longest Palindromic Subsequence is %d", lps(seq.toCharArray(), 0, n - 1));
    }
}

 

 

Time Complexity: The time complexity for the above approach is 2ⁿ because in the worst case, we will either increment the ‘i’ pointer or decrement the ‘j’ pointer and make two choices. 

 

Space Complexity:  The space complexity for the above approach is constant. We are not using any auxiliary space.

 

APPROACH 2:

We can optimize APPROACH 1 by memoizing it. We can create a 2D D.P. table of size (str.length()) * (str.length()) to store the answer for each ‘i’ and ‘j’ value because it might be possible that we try to compute the answer for the same ‘i’ and ‘j’ values multiple times.

 

Refer to the below recursion tree.

 

 

In the above recursion tree, we are calculating the value for func(1, 8) twice. Hence we can memoize it.

 

Refer to the below implementation for the above optimization.

 

class Main {
 
    //Initializing the DP table.
    static int dp[][];
    
    // A utility function to get the max of the giventwo integers
    static int max(int x, int y) {
        return (x > y) ? x : y;
    }
    
    // This function returns the length of the longest palindromic subsequence in arr
    static int lps(char arr[], int i, int j) {
        
        // Base Case 1: If only 1 character is there
        if (i == j) {
            return 1;
        }
        
        // Base Case 2: If only 2 characters are there and both are same
        if (arr[i] == arr[j] && i + 1 == j) {
            return 2;
        }
        
        /* 
          If the current state is
          already pre-computed
        */
        if(dp[i][j] != -1){
            return dp[i][j];
        }
        
        // If the first and last characters match
        if (arr[i] == arr[j]) {
            return dp[i][j] = lps(arr, i + 1, j - 1) + 2;
        }
 
        // If the first and the last characters do not match
        return dp[i][j] = max(lps(arr, i, j - 1), lps(arr, i + 1, j));
    }
 
 
    public static void main(String[] args) {
        String seq = "ZXYFYKXAC";
        int n = seq.length();
        
        dp = new int[n][n];
        
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                dp[i][j] = -1;
            }
        }
        
        System.out.printf("The length of the Longest Palindromic Subsequence is %d", lps(arr.toCharArray(), 0, n - 1));
    }
}

 

 

Time Complexity: The time complexity for the above approach is O(N * N) because we are maintaining a DP table to store the answer for different (i, j) pairs. Hence, we will never calculate the answer for the already calculated (i, j) pair.

 

Space Complexity:  The space complexity for the above approach is O(N * N) because we maintain a 2D D.P. table of size O(N * N).

 

APPROACH 3:

We can also write the above memoized recursive approach in an iterative manner using the bottom-up D.P. approach. We can create a 2D D.P. similar to the second approach of size (N * N) to store the answer for each ‘i’ and ‘j’ pair.

 

class Main {
    
    // A utility function to get the max of the two integers
    static int max(int x, int y) {
        return (x > y) ? x : y;
    }
    
    // Returns length of the longest palindromic subsequence in s
    static int lps(char s[]) {
        
        int n = s.length;
        
        //Initializing the DP table.
        int dp[][] = new int[n][n];
        
        for(int g = 0;g < n;g++){
            for(int i = 0,j = i+g;j < n;j++,i++){
                if(g == 0) {
                    dp[i][j] = 1;
                }
                else if(g == 1) {
                    if(s[i] == s[j]) {
                        dp[i][j] = 2;
                    }
                    else {
                        dp[i][j] = 1;
                    }
                }
                else{
                    if(s[i] == s[j]) {
                        dp[i][j] = 2 + dp[i+1][j-1];
                    }
                    dp[i][j] = max(dp[i][j], max(dp[i+1][j], dp[i][j-1]));
                }
            }
        }
        
        //return the value at topmost right index
        return dp[0][n-1];
    }
 
 
    public static void main(String[] args) {
        String seq = "ZXYFYKXAC";
        int n = seq.length();
        
        System.out.printf("The length of the LPS is %d", lps(seq.toCharArray()));
    }
}

 

 

Time Complexity: The time complexity for the above approach is O(N * N) because we are running two nested for loops of O(N) time, making the overall time complexity to be O(N * N).

 

Space Complexity:  The space complexity for the above approach is O(N * N) because we maintain a 2D D.P. table of size O(N * N).

 

FAQs:

What optimization did we do on the recursive approach for the Longest Palindromic Subsequence problem?

Since we were computing the answer for the same state at different times, we made a DP table to store the answer for the states we had already calculated. If we need the answer for the same state in the future, we can directly return the answer from the DP table.

 

What is the time complexity for the optimized approach of the Longest Palindromic Subsequence problem?

The time complexity for the optimized approach is O(N * N) because we are storing the answer for all possible ‘i’ and ‘j’ pairs, and if we have already calculated the answer for any recursion call, we return its answer stores in the DP table.

 

Can we apply a similar approach for the Longest Palindromic Subsequence problem if the array length has its maximum value of 10⁵?

If we apply a similar approach for the mentioned constraints, the compiler will give us the ‘Memory Limit Exceeded’ error because of forming the DP table.

 

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the Recursive approach to solve the Longest Palindromic Subsequence problem.
  2. Then we saw how we optimized the approach by memoizing using the DP table.

 

Suppose you want to learn more about Dynamic Programming and practice some questions that require you to take your basic knowledge on Dynamic Programming a notch higher. In that case, you can visit our Guided Path for Dynamic Programming. To practice this problem, you can visit Practice Problem.



BY: NISHANT RANA

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think