Longest Common Subsequence

Posted: 23 Mar, 2017
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.

Try Problem