Table of Contents
If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
Given two Strings A and B. Find the length of the Longest Common Subsequence (LCS) of the given Strings.
Subsequence can contain any number of characters of a string including zero or all (subsequence containing zero characters is called as empty subsequence). Characters need not to be contiguous but must maintain the relative order as in the given String. We need to find the maximum length of this subsequence which has characters common to both the given Strings.
A : JAVABLOG
B : ABLGOUTPUT :
4
APPROACH – I (RECURSIVE):
We just need to find the maximum length of a sequence containing characters common to both the strings in the relative order same as that of the given Strings.
In this approach we calculate our result in bottom-up manner that is, while returning from recursion.
We keep on shortening the length of the given Strings by one character, and once we hit the basecase, this is the point where at least one of the two string is exhausted having size zero. So in this case we can not have any matching character in the two strings, therefore, we return 0.
As we know we kept on removing the first character of the string in every recursion state, now the result of the bigger string will depend on the result of these smaller Strings.
Now to find this, two possibilities arise :
Case 1 :
When the two characters match.
If the both the character matches then we can add 1 to the length of the LCS found till now and can return one plus the result of shortened strings which we will get from recursion.
that is, 1 + LCS( shortened A, shortened B)
Case 2 :
When the two characters do not match.
If the characters do not match, then there are chances are, that the first character of String A matches with some other character in B or the first character of B matches with some other character in A. But as we need our result to be maximum therefore we return the maximum of these two calls.
that is, Maximum of (LCS of shortened A & B) and (LCA of A and shortened B).
As at every point we are making two calls when the first character of the two strings does not match, therefore, in the worst case where there is no matching characters in either of the two strings, then in that case our worst time complexity will be O(2^n), where n is the length of the shorter String.
Consider an Example for better understanding and its recursion tree,
A : son
B : nop
As we can see, in the recursion tree, we make only one call for remaining Strings whenever the first character matches and in every other case we make two calls.
At every base case condition we are returning zero and we are returning one plus the result achieved from recursion whenever there is a match in the first two characters.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
package DynamicProgramming; import java.util.Scanner; public class LongestCommonSubs { public static void main(String[] args) { Scanner scn = new Scanner(System.in); String A = scn.nextLine(); String B = scn.nextLine(); System.out.println(LCS(A, B)); } public static int LCS(String A, String B) { /*if one String is exhausted or is empty then * there can not be any matching characters in * string A and B*/ if(A.length()==0||B.length()==0) { return 0; } /*As on this state of recursion we are working * on first characters of strings, in next recursion * we need to recur for remaining strings with first * characters removed */ String remA = A.substring(1); String remB = B.substring(1); /* if the current first characters of both strings * matches then we add 1 to the LCS length and then * recur to find answer for remaining Strings*/ if(A.charAt(0)==B.charAt(0)) { int remRes = LCS(remA, remB); return 1 + remRes; } else { /*if the current first characters of both strings * does not match, then maximum length of LCS of * current string will be the max LCS of * (remaining A and B) or (A and remaining B) */ int remRes = Math.max(LCS(remA, B), LCS(A, remB)); return remRes; } } } |
Approach – II : Dynamic Programming:
We can clearly see the duplication of the calls represented by red colour in the recursion tree where result of same problem is getting calculated again. These Overlapping Subproblems are leading to an increase in Time Complexity of this algorithm.
Also, The result of bigger problem can be calculated with the help of results of smaller subproblems as we discussed in the recursive approach how we calculated the maximum length of LCS of a bigger string with the help of results of the smaller (shortened) strings.
As this problem has both the properties of Dynamic Programming, that is, Overlapping subproblems and Optimal Substructure. Therefore, we can use an approach involving dynamic programming to efficiently solve this problem.
We keep a Two – Dimensional matrix DP[][] of length (N+1) x (M+1) where N and M are the lengths of two given Strings A and B. Any cell DP[i][j] will represent the maximum length of LCS of two substrings, that is, A[1...i] & B[1...j], where A and B are the two given Strings.
Base cases would be the problems whose solution is known without any further computation. In this approach,
DP[0][j] = 0 and DP[i][j] = 0 wherein both the cases atleast one string has length zero and in that case LCS would obviously be zero. Also to store this base case result, Length of DP matrix is one plus the length of given Strings.
The final result of this problem will be on the cell DP[N][M] as this cell represents the LCS of
strings A[1...N] & B[1...M], where A and B are the two given Strings and N & M are their lengths respectively.
Discussion of Optimal Substructure :
CASE-1 :
We know, if the first character of the current strings/ substrings matches then we make call for the shortened strings and add one to the LCS being calculated as the current characters match.
Similarly here in this DP approach, if A[i] = B[j] that is, character at ith position in A matches with character at jth position in B, then,
DP[i][j] = 1 + DP[i-1][j-1]
DP[i-1][j-1] is cell where the result of shortened string lies, that is, A[1…i-1] and B[1…j-1]
Case-2:
if the first character of the current strings/ substrings does not match then we made two separate calls in recursive approach and final length of LCS is the result of Maximum of those two calls.
Similarly, in this DP approach if A[i] != B[j] then,
DP[i][j] = max (DP[i-1][j] , DP[i][j-1])
where,
DP[i-1][j] contains the maximum Length of LCS of A[1...i-1] and B[1...j] and,
DP[i][j-1] contains the maximum Length of LCS of A[1...i] and B[1...j-1].
Discussion of time complexity :
As we use a Matrix of size N X M where N and M are the lengths of the given two strings, and as we progress we calculate result for every cell.
That is why, the Worst time complexity of this approach for solving this problem would be O(NM).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
package DynamicProgramming; import java.util.Scanner; public class LongestCommonSubs { public static void main(String[] args) { Scanner scn = new Scanner(System.in); String A = scn.nextLine(); String B = scn.nextLine(); System.out.println(LCS(A, B)); } public static int LCS(String A, String B) { /* matrix for storing results of the subproblems, size is * one more than the string length to store the base case * results*/ int[][] dp = new int[A.length() + 1][B.length() + 1]; for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[0].length; j++) { /*checking characters at index - 1 as 0th character * of given String is at 1st index in DP matrix */ if (A.charAt(i-1) == B.charAt(j-1)) { /*optimal substructure as explained in the article*/ dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[A.length()][B.length()]; } } |
That’s all about Longest common Subsequence in java.
