Do you think IIT Guwahati certified course can help you in your career?
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.
classMain { // A utility function to find the max of two given integers. staticintmax(int x, int y) { return (x > y) ? x : y; } // Returns the longest palindromic subsequence in the arr array staticintlps(char arr[], int i, int j) { // Base Case 1: If only 1 character present if (i == j) { return1; } // Base Case 2: If only 2 characters are present and both same if (arr[i] == arr[j] && i + 1 == j) { return2; } // 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)); } publicstaticvoidmain(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.
classMain { //Initializing the DP table. staticint dp[][]; // A utility function to get the max of the giventwo integers staticintmax(int x, int y) { return (x > y) ? x : y; } // This function returns the length of the longest palindromic subsequence in arr staticintlps(char arr[], int i, int j) { // Base Case 1: If only 1 character is there if (i == j) { return1; } // Base Case 2: If only 2 characters are there and both are same if (arr[i] == arr[j] && i + 1 == j) { return2; } /* 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)); } publicstaticvoidmain(String[] args) { String seq = "ZXYFYKXAC"; int n = seq.length(); dp = newint[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.
classMain { // A utility function to get the max of the two integers staticintmax(int x, int y) { return (x > y) ? x : y; } // Returns length of the longest palindromic subsequence in s staticintlps(char s[]) { int n = s.length; //Initializing the DP table. int dp[][] = newint[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; } elseif(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]; } publicstaticvoidmain(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).
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:
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
Live masterclass
Become a YouTube Analyst: Use Python to analyze viewers data
by Coding Ninjas
04 Feb, 2025
02:30 PM
Get hired as an Amazon SDE : Resume building tips
by Coding Ninjas
03 Feb, 2025
02:30 PM
Expert tips: Ace Leadership roles in Fortune 500 companies
by Coding Ninjas
03 Feb, 2025
12:30 PM
Become a YouTube Analyst: Use Python to analyze viewers data
85+ registered