Longest Palindromic Subsequence using Dynamic Programming

Posted in

Longest Palindromic Subsequence using Dynamic Programming
vinaykhatri

Vinay Khatri
Last updated on April 25, 2024

    Problem Statement

    You are given a String ‘ S’ of a certain length, your task is to find the maximum possible palindromic subsequence that can be obtained from the given string.

    Subsequence

    A subsequence of a given string is generated by deleting some characters of that string without changing its order.

    Example 1:

    Input: S = "ABBDCACB"
    Output: 5

    Explanation: From the above string, the Longest possible palindromic subsequence is 5, and the subsequence of the string is “BCACB”.

    Example 2:

    Input: S = "ANMAQRSLAGHYAGHLAM"
    Output: 9

    Explanation: From the above string, the longest possible palindromic subsequence is 9, and the subsequence of the string is "MALAYALAM."

    Approach

    In the above problem statement, we are asked to find out the maximum palindromic subsequence that can be obtained from the given string. So, if we could observe the problem statement very keenly, we can encounter that the problem has optimal substructure and overlapping subproblem properties.

    Optimal Substructure

    A given problem has Optimal Substructure Property if an optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

    Overlapping Subproblems

    Dynamic Programming, like Divide and Conquer, combines solutions to sub-problems. Dynamic Programming is primarily used when solutions to the same subproblems are required repeatedly. Computed solutions to subproblems are stored in a table in dynamic programming so that they do not have to be recomputed. So, if there are no common (overlapping) subproblems, Dynamic Programming cannot be used because storing the solutions is pointless if they are never needed again.

    Approach 1: (Recursion)

    This approach is called the naive approach, the idea is to implement the Recursion. For implementing the recursion, we will have two cases:

    1. If the first and last characters of the strings are the same, then we increment the counter (which means that we had obtained a palindrome) and increment the i pointer and decrement the j pointer
    2. Consider a situation where the first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values.

    We get the maximum value of the string as stated below:

    1. Deleting the first character and applying the recursion for the remaining entire string S[i+1,j]
    2. Deleting the last character and applying the recursion for the remaining entire string S[i,j-1]

    From the above two cases, we are going to pick the maximum value (i.e, maximum palindromic subsequence, which is obtained from the string S).

    Time Complexity

    For the Naive Approach, the time complexity is going to be as 2^n, as the function call happens for every subroutine.

    Note

    One thing to be kept in mind is that we should define the base case properly; it may result in a Recursion Depth Exceeded exception.

    Recursion calls

    From the above figure, we can understand that recursion has to take place for every subroutine call so this may take a huge time to run and to solve the hierarchical model. This is the main reason why we have the time complexity as 2^n.

    Below is the Algorithm Explained

    Define a function called longest palindromic subsequence and take two Pointers as i and j and assign them at the 0th position of the string and last posting the string, respectively. Now define the base cases stated below:

    Base cases

    1. If S[i]==S[j] (this means that, palindrome encountered), then we will return 1.
    2. If i > j , this means that if the i pointer exceeds the j pointer, we will simply terminate the process and return 0.

    If the S[i] and S[j] are not equal, we will apply the recursion by considering the two possibilities discussed above.

    Python Code Using Recursion

    # Function to find the Maximum length of the  palindromic subsequence
    # of given string
    def longestPalindromicsubsequence(S, i, j):
    
        # Base case
        if i > j: # if i exceeds the  j pointer
            return 0 # stop the flow
    
        # If the string `S" has only one  Unique char, it is a palindrome
        if i == j:
            return 1 # the maximum length is 1 so we return 1
    
        # If the last character of the string  matches the  first character
        if S[i] == S[j]:
            # include the first and last characters in palindrome
            # and apply the recursion  for the remaining substring `S[i+1, j-1]`
            return longestPalindromicsubsequence(S, i + 1, j - 1) + 2
    
        '''
         Consider a situation where the   first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
    
    We get the maximum value of the string as stated below:
    
    Deleting the first character and apply the recursion for the remaining  entire string S[i+1,j]
    Deleting the last character and apply the recursion for the remaining entire string S[i,j-1]
    
        '''
    
        # we will simply Return the maximum of the two possible values
        return max(longestPalindromicsubsequence(S, i, j - 1), longestPalindromicsubsequence(S, i + 1, j))
    
    
    if __name__ == '__main__': # main function
    
        S = "ABBDCACB" # input of the string
        n = len(S) # length of the string
    
        print("The longest palindromic subsequence length  is",
           longestPalindromicsubsequence(S, 0, n - 1))

    Output:

    'The longest palindromic subsequence length  is', 5

    Java Code Using Recursion

    public class Main // defining the main class
    {
        //defining the function to find  the longest palindromic subsequence
        // of a string of given S
        public static int  longestPalindromicsubsequece(String S, int i, int j)
        {
            // Base case
            if (i > j) {  // if the i pointer  exceeds the j pointer 
                return 0;
            }
     
            // If the string S has only one unique char, it is a palindrome
            if (i == j) {
                return 1;// we will return 1 
            }
     
            // If the first  character of the string  matches the second  character,
            if (S.charAt(i) == S.charAt(j))
            {
                //  then we will include the first and last characters in palindrome
                // and apply recursion  for the remaining substring `S[i+1, j-1]`
                return longestPalindromicsubsequece(S, i + 1, j - 1) + 2;
            }
     
            /*
              If the first character of the string does not match the last character then we will 
                1. Delete  the last character and apply recursion  for the remaining part of the string left
                   `S[i, j-1]`
                2. Delete  the first character and apply recursion  for the remaining substring left
                   `S[i+1, j]`
            */
     
            return Integer.max( longestPalindromicsubsequece(S, i, j - 1), // we will pick the maximum value
                         longestPalindromicsubsequece(S, i + 1, j));
        }
     
        public static void main(String[] args)
        {
            String S = "ABBDCACB";
            int n = S.length();
     
            System.out.print("The length of the longest palindromic subsequence is "
                    +  longestPalindromicsubsequece(S, 0, n - 1));
        }
    }
    

    Output:

    The length of the longest palindromic subsequence is 5

    C++ Version Code Using recursion

    #include<bits/stdc++.h>
    using namespace std;
    
    // defining a function to return the  max of two integers
    int max (int x, int y) { return (x > y)? x : y; }
    
    // Returns the length of the maximum  palindromic subsequence of a given string
    int longestpalindromicsubsequence(char *S, int i, int j)
    {
    // If there is only 1 unique  character then we will return 1
    if (i == j) // since it is a palindrome
    	return 1;
    
    //2nd base condition, is if there are only two characters present 
    if (S[i] == S[j] && i + 1 == j)
    	return 2; // then we will return 2  since the length of the the maximum length of the palindromic Subsequence is 2
    
    // If the first and last chars are equal
    if (S[i] == S[j])
    	return longestpalindromicsubsequence (S, i+1, j-1) + 2;
    
    // If the first char and last char dosentare not equal then we will picj the maximum value
    return max( longestpalindromicsubsequence(S, i, j-1), longestpalindromicsubsequence(S, i+1, j) );
    }
    
    /* Driver program to test above functions */
    int main()
    {
    	char S[] = "ABBDCACB";
    	int n = strlen(S);
    	cout << "The length of the Longest  Palindromic Subsequence  is "<< longestpalindromicsubsequence(S, 0, n-1);
    	return 0;
    }

    Output:

    The length of the Longest  Palindromic Subsequence  is 5

    Approach 2: (Dynamic Programming)

    This approach is efficient. Since there exists the optimal overlapping property, we can comfortably implement the Dynamic Programming Approach.

    The Main Difference between the Recursion and Dynamic Programming Approach is

    In the dynamic programming approach, we will not revisit the computed subroutine, instead, we will save all the computed values in an array and if we encounter the same recursive call to be computed again and again, we will simply make use of the functional value from the table. This approach is called Memoization.

    Explanation of Memoization with an example

    By Looking at the Figure of recursive calls, we see that while solving the recursive calls (1,5) and (0,4), we get (1,2) as a common recursive call to be computed again and again, so this may consume much more time, to avoid this time consuming, we simply store the value of (1,2) in an array or dictionary. So whenever we again require this value to be computed, we will simply reuse it from the stored array. In this way, we can save a huge amount of time, and we can even reduce the complexity of any algorithm respectively, this is called Dynamic Programming.

    Dynamic Programming Algorithm

    The Complete Algorithm is the same as the recursive one, and one extra functionality added to this is we will declare an extra key functionality to store pre-computed values.

    The complexity of Dynamic programming:

    • Time Complexity : O(N^2)
    • Space Complexity: O(N^2)

    Where N is the length of the Input string.

    Note : One thing that is to be kept in mind is that we should define the base case properly else, it may result in Recursion Depth Exceeded the exception.

    Python Version Of Dynamic programming

    # definition function longestpalandromicstring
    def longestpalandromicstring(S, i, j,array):
     
        # Base case 
        if i > j: # if the i pointer exceeds j pointer then we return 0 
            return 0
     
        # If the two pointers are equal means, one unique  character is present 
        if i == j:
            return 1 # then we return 1 
     
        # declaring the key to store the computation calls
        key = (i, j)
     
        # we will check the key, before its computation into the array
        if key not in array: # if it is not present then only we will start the recursion function
     
            
     
            if S[i] == S[j]: # if its matches 
                array[key] = longestpalandromicstring(S, i + 1, j - 1,array) + 2
            else:
                '''      Consider a situation where the   first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
    
    We get the maximum value of the string as stated below:
    
    Deleting the first character and apply the recursion for the remaining  entire string S[i+1,j]
    Deleting the last character and apply the recursion for the remaining entire string S[i,j-1]
     '''
     
                array[key] = max(longestpalandromicstring(S, i, j - 1, array),
                                longestpalandromicstring(S, i + 1, j, array))
     
        # Return the subproblem solution from the dictionary
        return array[key]
     
     
    if __name__ == '__main__':
     
        S = "ABBDCACB"
        n = len(S)
     
        # Create a dictionary to store solutions to subproblems
        array = {}
     
        print("The maximum longest palindromic subsequence is",
            longestpalandromicstring(S, 0, n - 1, array))

    Output:

    The maximum longest palindromic subsequence is 5

    Java Version using Dynamic Programming

    import java.util.HashMap;
    import java.util.Map;
     // defining the main class
    public class Main
    {
        
        public static int longestPalindromestring(String S, int i, int j,
                                            Map<String, Integer> map) // defining the longest palindromic string function 
        {// additionally we also declare a hashmap to map the precomputed elements 
            // Base case
            if (i > j) { // if i pointer exceeds the j pointer
                return 0; // we return 0
            }
     
            // If the string `S`contains  only one unique  character, it is a palindrome
            if (i == j) {
                return 1; // we return 1 since a palindrome is found
            }
     
            // we will now built the unique key to map the elements
            String key = i + "|" + j;
     
            // for the first time store  every precomputed value in the map and check for each recursive call
            if (!map.containsKey(key)) // whether it contains the value or not 
            {
                /* If the last character of the string is the same as the first character,
                   include the first and last characters in palindrome and recur
                   for the remaining substring `X[i+1, j-1]` */
     
                if (S.charAt(i) == S.charAt(j)) { // if the  palindrome is detected, then increment the value by 2
                    map.put(key, longestPalindromestring(S, i + 1, j - 1, map )+ 2);
                }
                else {
     
                    /*    Consider a situation where the   first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
    
    We get the maximum value of the string as stated below:
    
    Deleting the first character and apply the recursion for the remaining  entire string S[i+1,j]
    Deleting the last character and apply the recursion for the remaining entire string S[i,j-1]
     */
     
                    map.put(key, Integer.max(longestPalindromestring(S, i, j - 1, map), // simply choose the max value
                                                longestPalindromestring(S, i + 1, j, map)));
                }
            }
     
            // Return the precomputed subroutine
            return map.get(key);
        }
     
        public static void main(String[] args)
        {
            String S = "ABBDCACB";
            int n = S.length();
     
            // Create a map to store the precomputed solutions
            Map<String, Integer> array = new HashMap<>();
     
            System.out.print("The maximum longest palindromic subsequence is  " +
                                    longestPalindromestring(S, 0, n - 1, array));
        }
    }

    Output :

    The maximum longest palindromic subsequence is  5

    C++ Version Using Dynamic Programming

    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
     
    // defining the function to find the maximum longest palindrome subsequence
    int longestPalindromestring(string S, int i, int j, auto &map)
    {
        // Base condition
        if (i > j) { // if i pointer exceeds j pointer
            return 0; // we will return 0
        }
     
        // If the string string 'S' has only one character, then a palindrome is detected
        if (i == j) {
            return 1; // we will return 1
        }
     
        //we will built a key to store the precomputed values
        string key = to_string(i) + "|" + to_string(j);
     
        // if you encounter the subroutine for the first time then solve it and store it in the map  s we discussed in the above approach
        if (map. find(key) == map. end())
        {
            // if the first and last character are equal, then we will add 2 and increment the i pointer and decrement the j pointer
            if (S[i] == S[j]) 
    {
                map[key] = longestPalindromestring(S, i + 1, j - 1, map) + 2;
            }
            else {
     
                /*   Consider a situation where the   first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
    
    We get the maximum value of the string as stated below:
    
    Deleting the first character and apply the recursion for the remaining  entire string S[i+1,j]
    Deleting the last character and apply the recursion for the remaining entire string S[i,j-1]
     */
     
                map[key] = max (longestPalindromestring(S, i, j - 1, map), // we will simply pick the maximum value
                            longestPalindromestring(S, i + 1, j, map));
            }
        }
     
        //return the subroutine recursive call
        return map[key];
    }
     
    int main()
    {
        string S = "ABBDCACB";
        int n = S.length();
     
        // Create a map to store the subroutine
        unordered_map<string, int> map;
     
        cout << "The length of the longest palindromic subsequence is " <<longestPalindromestring(S, 0, n  1, map);
     
        return 0;
    }

    Output:

    The Maximum Longest Palindromic Subsequence is  5.

    Now we will see how to trace and print the Longest Palindromic Subsequence of the given string.

    Algorithm

    Here, we'll look at how to print the longest palindromic subsequence. The Longest Common Subsequence (LCS) problem is similar to this one. We can solve this problem by using LCS as a subroutine. The LCS-based two-step solution is shown below. 1) Reverse the given sequence and save it in a new array called rev[0..n-1]. 2) The given sequence's LCS and rev[] will be the palindromic series that is the longest. 3) Once we've located LCS, we can print it.

    Below is the Approach

    Python version Dynamic programming

    # The LCS problem is implemented using dynamic programming.
    
    # Returns the LCS length for STRING1[0..m-1], STRING2[0..n-1], and STRING2[0..n-1].
    def lcs(X, Y, m, n):
    	array = [[0 for x in range(n+1)] for x in range(m+1)]
    
    #Construct the array [m+1][n+1] from the bottom up using the steps below.
    	for i in range(m+1):
    		for j in range(n+1):
    			if i == 0 or j == 0:
    				array[i][j] = 0
    			elif string1[i-1] == string2[j-1]:
    				array[i][j] = array[i-1][j-1] + 1
    			else:
    				array[i][j] = max(array[i-1][j], array[i][j-1])
    
    # To print LCS, use the code below.
    	index = array[m][n]
    
    	# To store the lcs string, construct a character list.
    	lcs = [""] * (index+1)
    	lcs[index] = ""
    
    	#Begin at the right-most-bottom-most corner and 
    	#store characters in lcs[] one by one.
    	j = n
    	while i > 0 and j > 0:
    
    	#If the current character in X[] and Y[] is the same, then the current character belongs to LCS.
    		if string1[i-1] == string2[j-1]:
    			lcs[index-1] = string1[i-1]
    			i-=1
    			j-=1
    			index-=1
    
    	#If the values are not equal, find the larger of the two and proceed in the direction of the larger value.
    		elif array[i-1][j] > array[i][j-1]:
    			i-=1
    		else:
    			j-=1
    
    	print("LCS of " + string1 + " and " + string2 + " is " + "".join(lcs))
    
    # Driver program
    string1 = "ABBDCACB"
    string2 = 'BCACDBBA' # reverse of string1
    m = len(string1)
    n = len(string2)
    lcs(string1, string2, m, n)

    Output:

    LCS of ABBDCACB and BCACDBBA is BCACB

    Java Version of Dynamic Programming

     // defining the Function to print longest palindromic subsequence of string `string1[0…m-1]` and `string2[0…n-1]`
    public class  palindromicsubsequence { 
      
     /* LCS string1 and string2 are returned */
        static String lcs(String string1, String string2) { 
            int m = string1.length(); 
            int n = string2.length(); 
            char X1[] = string1.toCharArray(); 
            char Y1[] = string2.toCharArray(); 
      
            int table[][] = new int[m + 1][n + 1]; 
      
    /* Construct table[m+1][n+1] from the bottom up using the steps below. Table[i][j] includes the lengths of string1[0..i-1] and string2[0..j-1] LCS. */
    
            for (int i = 0; i <= m; i++) { 
                for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { table[i][j] = 0; } else if (X1[i - 1] == Y1[j - 1]) { table[i][j] = table[i - 1][j - 1] + 1; } else { table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]); } } } // To print LCS, use the code below. int pointer = table[m][n]; // Make a String of index+1 length and fill it with it char[] lcstore = new char[pointer + 1]; // Begin at the right-most-bottom-most / corner and store characters in lcstore[] one after the other. int i = m, j = n; while (i > 0 && j > 0) { 
               //If the current character in string1[] and string2 are the same, then the current character is part of the LCStore.
                if (X1[i - 1] == Y1[j - 1]) { 
                    // insert the  character in result  
                    lcstore[pointer - 1] = X1[i - 1]; 
                    i--; 
                    j--; 
      
                    // decrement the  of i, j and pointer  values
                    pointer--; 
                } //If the two values are not equal, find the larger of the two and proceed in the direction of the larger / value.
                else if (table[i - 1][j] > table[i][j - 1]) { 
                    i--; 
                } else { 
                    j--; 
                } 
            } 
            String answer = ""; 
            for (int x = 0; x < lcstore.length; x++) { answer += lcstore[x]; } return answer; } // Returns str's longest palindromic subsequence. static String lps(String str2) { //Find the opposite of str. String rev = str2; rev = reverse(rev); // Return the LCS of str as well as its inverse. return lcs(str2, rev); } static String reverse(String str3) { String answer = ""; //toCharArray() converts a String to a character array. char[] try1 = str3.toCharArray(); for (int i = try1.length - 1; i >= 0; i--) { 
                answer += try1[i]; 
            } 
            return answer; 
        } 
      
    /* Test driver programme for the above identified feature */
        public static void main(String[] args) { 
            String str1 = "ABBDCACB"; 
            System.out.println(lps(str1)); 
      
        } 
    } 

    C++ Version Of Dynamic Programming

    /* c++ program to trace the longest palindromic subsequence */
    #include<bits/stdc++.h>
    using namespace std;
    
    /* Returns LCS of string1 and string2 */
    string  longestcommonsubsequence(string &string1, string &string2)
    {
    	int m = string1.length();
    	int n = string2.length();
    
    	int table[m+1][n+1];
    
    /* In the following steps, construct the table [m+1][n+1] in a bottom-up fashion. It is worth noting that table[i][j] contains the length of LCS for strings1[0..i-1] and string2[0..j-1]. */
    	for (int i=0; i<=m; i++)
    	{
    		for (int j=0; j<=n; j++) { if (i == 0 || j == 0) table[i][j] = 0; else if (string1[i-1] == string2[j-1]) table[i][j] = table[i-1][j-1] + 1; else table[i][j] = max(table[i-1][j], table[i][j-1]); } } // The code below is used to print LCS. int index1 = table[m][n]; // Make a string of index+1 length and assign all zeros to string lcsequence(index+1, '0'); string longestcommonsubsequence(index1+1, '\0'); int i = m, j = n; while (i > 0 && j > 0)
    	{
    			// If current character in string1[] and string2 are same, then current character ti is said that,it  is the  part of LCS
    		if (string1[i-1] == string2[j-1])
    		{
    		// insert the current char into the result
    			longestcommonsubsequence[index1-1] = string1[i-1];
    			i--;
    			j--;
    
    		// start reducing the values i,j,index
    			index1--;
    		}
    
    		
    		// if they are not same then find the largest of them
    		else if (table[i-1][j] > table[i][j-1])
    			i--;
    		else
    			j--;
    	}
    
    	return  longestcommonsubsequence;
    }
    
    
    // this function returns the longest palindromic subsequence
    
    string lps(string &str1)
    {
    	// reverse of the given input string is found
    	string rev = str1;
    	reverse(rev.begin(), rev.end());
    
    // we will now return the reverse of the string
    	return longestcommonsubsequence(str1, rev);
    }
    
    // Driver code
    int main()
    {
    	string str1 = "ABBDCACB";
    	cout << lps(str1);
    	return 0;
    }

    Conclusion

    1. In the above article, we have learned the following basic things:
      1. What is a subsequence?
      2. What is an optimal substructure?
      3. What is the overlapping subproblem property?
    2. We have also learned about the detailed procedure to solve the Longest palindromic subsequence along with its path.
    3. We did so using the Naive Approach and the Dynamic Programming Approach.

    We hope that you will now be able to solve this problem, as well as its variants, without any difficulty.

    People are also reading:

    Leave a Comment on this Post

    0 Comments