The longest palindromic subsequence (LPS) problem is the problem of finding the longest subsequence of a string (a subsequence is obtained by deleting some of the characters from a string without reordering the remaining characters) which is also a palindrome. In general, the longest palindromic subsequence is not unique. For example, the string alfalfa has four palindromic subsequences of length 5: alala, afafa, alfla, and aflfa. However, it does not have any palindromic subsequences longer than five characters. Therefore all four are considered longest palindromic subsequences of alfalfa.
Lets first solve the problem using Recursion:
package askgif.dp;
public class LongestPalindromicSubsequence {
public static void main(String[] args) {
String str = "bbbab";
long startTime = System.nanoTime();
System.out.println(FindLongestSubsequenceLen(str, 0, str.length()-1));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindLongestSubsequenceLen(String str,int start, int end) {
if(start > end)
return 0;
if(start == end)
return 1;
if(str.charAt(start) == str.charAt(end))
return 2 + FindLongestSubsequenceLen(str, start+1, end-1);
return max(FindLongestSubsequenceLen(str, start+1, end),
FindLongestSubsequenceLen(str, start, end-1));
}
private static int max(int a, int b) {
return a>b?a:b;
}
}
output:
4
Total Time (nanoseconds) : 233345
If you look at the solution closely you will find that many of the subproblems are getting repeated and the time complexity of the above solution is exponential. i.e O(2^n)
Can we solve the above problem in a more efficient way?
Yes, by using Dynamic Programming.
package askgif.dp;
public class LongestPalindromicSubsequence {
public static void main(String[] args) {
String str = "bbbab";
long startTime = System.nanoTime();
System.out.println(FindLongestSubsequenceLen(str));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindLongestSubsequenceLen(String str) {
int[][] dp = new int[str.length()+1][str.length()+1];
int j = 0;
for(int len=0;len<str.length();len++) {
for(int i=0;i<str.length()-len;i++) {
if(len == 0)
dp[i][i] = 1;
else {
j = i+len;
if(str.charAt(i)==str.charAt(i+len)) {
dp[i][j]=dp[i+1][j-1] + 2;
}
else {
dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
}
}
}
}
return dp[0][str.length()-1];
}
private static int max(int a, int b) {
return a>b?a:b;
}
}
output:
4
Total Time (nanoseconds) : 484436
The time complexity of the above solution is O(n^2).
