The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to a set of sequences.
Given two sequences s1, s2, the task is to find the length of the longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order but is not necessarily contiguous.
Input: s1=ABCDGH, s2=AEDFHR Output: 3
Input: s1=AGGTAB, s2=GXTXAYB Output: 4
Solutions
Method 1: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "n" and "m" (length) changes, so we can store and reuse the result of a function(..n, m..) call using a "n * m" 2-D array.
The 2-D array will store a particular state (n, m) if we get it the first time.
Now, if we come across the same state (n, m) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n * m).
In addition, O(n * m) auxiliary space was used by the table.
Method 2: Recursion
The idea is to generate all subsequences of both given sequences and find the longest matching subsequence.
Start from the last elements (n-1, m-1) of both subsequences:
If s1[n-1] == s2[m-1], this character will be part of the longest subsequences, so add it to the count and check for the remaining (0...n-2, 0...m-2) characters.
If s1[n-1] == s2[m-1], then check recursively for (0...n-2, 0...m-1) and (0...n-1, 0...m-2) and return the max of these two.
If any of the subsequences is exhausted (m ==0, n ==0) return 0. This is the base condition.
Complexity
This solution is exponential O(2^(m+n)) in term of time complexity.
In addition, O(n) auxiliary stack space was used for the recursion stack.