Last Updated: 23 Mar, 2017
Longest Common Subsequence
Moderate
Asked in companies
Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'.
For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K.
Example :
Subsequences of string "abc" are: ""(empty string), a, b, c, ab, bc, ac, abc.
Input format :
The first line of input contains the string 'S' of length 'M'.
The second line of the input contains the string 'T' of length 'N'.
Output format :
Return the length of the Longest Common Subsequence.
Constraints :
0 <= M <= 10 ^ 3
0 <= N <= 10 ^ 3
Time Limit: 1 sec
Approaches
Let the two strings be x and y.
Let x(i) be the substring of x from index 0 to index i.
Let c[i, j] be the length of the longest common subsequence of strings x(i) and y(j).
Then the recurrence relation to find c[i, j] is as follows:
We can use this relation to write a simple recursive program but instead of recomputing the results of subproblems, compute them just once and store their results in a lookup table (Hashmap). Then whenever we would need to find the result of a subproblem, first we'll look for it in our table, if it's present then simply return it, otherwise use recursion to find the answer and then store it in the table.
Let the two strings be x and y.
Let x(i) be the substring of x from index 0 to index i.
Let c[i, j] be the length of the longest common subsequence of strings x(i) and y(j).
Then the recurrence relation to find c[i, j] is as follows:
Instead of making a lookup table and using recursion, make a 2D array, 'dp', of size (m + 1) * (n + 1) where, dp[i][j] will store the length of the LCS when you consider the first 'i' letters of the first string and first 'j' letters of the second string. Now, instead of getting results of subproblems from a lookup table, you can get them from the 2D array itself since you'll be filling it up, as you compute dp[m][n] starting from dp[0][0]
In each iteration of the outer loop in iterative ‘DP’ we only, need values from all columns of the previous row so instead of making an ('M' + 1) * ('N' + 1) sized array (referred to as the original array), just make a 2 * ('M' + 1) sized array (referred to as the new array).
When you compute the third row of the original array, copy its contents to the first row of the new array. Similarly, when you're computing the fourth row of the original array, copy its contents to the second row of the new array and so on.