Longest Common Subsequence
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

Question

Longest Common Subsequence

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

Accepted Answer

The task is to find the length of the longest common subsequence between two given strings.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
We can solve this problem using dynamic programming.
Create a 2D array to store the lengths of the longest common subsequences for all possible prefixes of the two strings.
Iterate through the strings and fill the array based on the following conditions: if the characters match, add 1 to the length of the previous longest common subsequence; otherwise, take the maximum of the lengths of the previous subsequences.
The last element of the array will contain the length of the longest common subsequence.

Accepted Answer

Memoization

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.

Space Complexity: O(1)Explanation:

O(m * n), where m and n are the lengths of each string

We are creating a lookup table of size (m*n)

Time Complexity: O(1)Explanation:

O(m * n), where m and n are the lengths of each string

We are maintaining a lookup table of size (m*n) and we will fill each cell of this table exactly once. Hence, total operations will be (m*n)

Accepted Answer

Iterative DP

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]

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(m*n) because we created an 2-D dp of m*n size.

Time Complexity: O(1)Explanation:

O(m*n) as there are m*n states of dp and we are filling each one of them exactly one time.

Accepted Answer

2 Rows Approach

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.

Space Complexity: O(n)Explanation:

O(M), Where ‘M’ is the length of the second string.

Since we are storing the array/list for the second string. Thus the space complexity will be O(M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(M * N), Where ‘M’ and ‘N’ are the lengths of each string.

Since we are traversing each of the element in both the string for each character of the other string. Thus the time complexity will be O(M * N).