In this article, we will look at yet another interesting problem popular in coding interviews. The problem states that Given a String we have to Find the Longest Palindromic Subsequence present in the String. We need to find only the Length of such subsequence. We will discuss various approaches related to our problem and analyze the time and space complexities.
By Subsequence, we mean a sequence of string characters not necessarily contiguous but they have to preserve their relative ordering. For Example, for the String : ABBHJ, AHJ is a subsequence of the string, because characters follow the order and each of them are present in the String. Now, we need to find a Palindromic Subsequence. E.g. For String, CBAFAB, BAAB and BAFAB are subsequences of the string and are palindrome. But Subsequence BAFAB is the longest among them with length 5.
Note: If a sequence of characters is contiguous it is a Substring. A substring is also a Subsequence.
Let us look at different approaches to solve this problem.
Approach 1 (Recursive Approach)
The Key steps to implement in this approach are:
- We have two pointers: Left Pointer: Contains start index of string, Right Pointer: Contains last index end of string. We first check if the given string is of length 1 i.e. if value of left and right are same we return 1 as a single character string is palindrome.
- Now, If the first character and the last character of the string matches, we add two to our result and recursively call for left+1 and right-1 index of the string.
- If the characters at left and right index do not match then we search for a palindromic string between indexes (left+1, right) and (left, right-1) of the string, we consider the length obtained from the maximum of the two for each recursive call and keep on adding them to the result until we reach the base case.
Input : DABCFCBAG Output : 7 // Here ABCFCBA IS Longest Palindromic Subsequence
Let us look at the code in Java:
class LongestPalindrome
{
// Returns the length of the Longest palindromic subsequence
static int longestPalindromeRecursive(String str, int left, int right)
{
// Boundary Check.
if (left > right) {
return 0;
}
//If there is only 1 character or left = right.
if(left == right)
return 1;
// If the characters at left and right index do match.
if (str.charAt(left) == str.charAt(right) )
{
return 2 + longestPalindromeRecursive(str,left+1,right-1);
}
// If the first and last characters do not match
return Math.max(longestPalindromeRecursive(str, left, right - 1), longestPalindromeRecursive(str, left + 1, right));
}
public static void main(String[] args) {
String str = "CBAFAB";
int n = str.length();
int result= longestPalindromeRecursive(str, 0, n - 1);
System.out.print("The Length of the Longest Palindrome is: "+result);
}
}
Output:
The Length of the Longest Palindrome is: 5
Time Complexity: We break each problem into 2 more sub problems in every recursive call. The time complexity is exponential in this case resulting O(2n ) complexity.
Approach 2 (Dynamic Programming)
We apply Dynamic Programming on Overlapping Subproblems. If there are problems which are computed again and again we can apply dynamic programming by storing results of previously occurred subproblems. This is the first property, the other one is Optimal Substructure, the problems whose final solution can be achieved by results of their subproblems. We see, both properties are evident in the recursive solution discussed above. So we apply Dynamic Programming. There are two approaches to discuss :
Top to Bottom Approach
In this approach we basically store the result of recursive solutions of each subproblem in a 2D Array for overlapping subproblems, to avoid repeated computations.
Let us look at the implementation of this approach in Java:
class LongestPalindrome
{
// Returns the length of the Longest palindromic subsequence
public static int longestPalindromeTop_To_Bottom(String str, int left, int right, Integer[][] arr)
{
//Boundary check
if(left > right)
return 0;
if(left == right) {
return 1;
}
if(arr[left][right] == null)
{
if(str.charAt(left) == str.charAt(right))
{
arr[left][right] = 2 + longestPalindromeTop_To_Bottom(str, left + 1, right - 1, arr);
}
else
{
arr[left][right] = Math.max(longestPalindromeTop_To_Bottom(str, left + 1, right, arr), longestPalindromeTop_To_Bottom(str, left, right - 1, arr));
}
}
return arr[left][right];
}
public static void main(String[] args)
{
String str = "CABEEBAF";
int n = str.length();
Integer arr[][]=new Integer[n][n];
int result= longestPalindromeTop_To_Bottom(str, 0, n - 1, arr);
System.out.print("The Length of the Longest Palindrome is: "+result);
}
}
Output:
The Length of the Longest Palindrome is: 6
Explanation: We use a 2D array to store the results obtained for each recursive call. We use Wrapper Class Integer array not primitive type because primitive type integer array initializes elements to zero. So to avoid confusion with our result which for some cases might give 0 we use it and Integer type array are initialized to null. So we check for the string with index left and right if the solution is not present in our array we recursively compute it (Like Previous Solution) and store it in our array. If the result is already computed we just return the result at index left and right. In such a case, there is no need of computing the same problem.
Time Complexity: The Time Complexity of this solution is O (n2), as we skip computing solutions of overlapping subproblems, we just return the already existing value. The complexity is not exponential in this case.
Space Complexity: We use a 2D array of size equal to length of the string, n so overall complexity is O(n2).
Bottom Up Approach
In this approach we will first solve the basic bottom solutions or base cases first, then we find the actual solution of subproblems and the whole problem. Here, we check each combination and get the maximum palindromic length. For each subsequence, we check how many palindromic subsequences are possible with it and get its maximum length. We can start from the start or end of the string.
This is an iterative approach, we fill the 2D array from the right diagonal half. Here, we fill the diagonal elements as 1 because a single character is a palindrome of length 1. So, apart from the diagonal elements if the left and right characters do not match then: Arr [left] [right]=Max( Arr[left+1] [right], Arr[left] [right-1] ).
If characters match then Arr[left][right]= 2+ Arr[left+1][right-1].
So, for the String ABEFBAC, The 2D array or tabulation look like this:
Note: We fill the table from the bottom and the max length is present at Arr[0] [n-1].
So let us have a look at the implementation of the above in Java:
class LongestPalindrome
{
// Returns the length of the Longest palindromic subsequence
public static int longestPalindromeBottomUp(String str, int n)
{
int[][] arr = new int[n][n];
// Initialize diagonal elements as 1.
for (int i = 0; i < str.length(); i++)
{
arr[i][i] = 1;
}
for(int left = n - 2; left >= 0; left--)
{
for(int right = left + 1; right < n; right++)
{
if(str.charAt(left) == str.charAt(right))
{
arr[left][right] = 2 + arr[left + 1][right - 1];
}
else
{
arr[left][right] = Math.max(arr[left + 1][right], arr[left][right - 1]);
}
}
}
// return the max length.
return arr[0][n - 1];
}
public static void main(String[] args)
{
String str = "ABEFBAC";
int n = str.length();
int result= longestPalindromeBottomUp(str, n);
System.out.print("The Length of the Longest Palindrome is: "+result);
}
}
Output:
The Length of the Longest Palindrome is: 5
Time Complexity: The complexity is O (n2) as above it is still effective being an iterative approach.
Space Complexity: It is O (n2), as we use a 2D array for the tabulation shown above.
So that’s it for the article you can try out the problem with different examples to test your understanding and execute the code too in your local compiler.
Feel free to leave suggestions or doubts (if any) in the comments section below.