Longest Common Subsequence
Learn to use dynamic programming in stringbased problems.
We'll cover the following
Problem statement
Given two sequences, 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.
For example, abc, abg, bdf, aeg, acefg…etc., are subsequences of abcdefg. So a string of length n
has ${2^{n}}$ different possible subsequences.
Solution: Naïve method
Let X be a sequence of length m
and Y be a sequence of length n
. Check if every subsequence of X is a subsequence of Y, and return the longest common subsequence found.
There are ${2^{m}}$ subsequences of X. To check whether or not the sequences are a subsequence of Y takes O(n) time. Thus, the naïve algorithm would take O(n.${2^{m}}$ ) time.
Let us consider an example to understand this problem better.

LCS for input Sequences ABCDGH and AEDFHR is ADH of length 3.

LCS for input Sequences AGGTAB and GXTXAYB is GTAB of length 4.
The naïve approach discussed above takes exponential time, which is why we need to find a way to optimize the solution. This problem can be solved using the dynamic programming approach (using Tabulation or Memoization).
Solution: Dynamic programming
Before moving on to implementation, let’s first look at the recurrence relation.
 If m = 0 or n = 0, then LCS(str1, str2, m, n) = 0. (Base case)
 If the last two characters of both strings are the same, i.e., if str1[m] = str2[n], then LCS(str1, str2, m, n) = 1 + LCS(str1, str2, m1, n1).
 Otherwise, LCS(str1, str2, m, n) = max{LCS(str1, str2, m1, n), LCS( str1, str2, m, n1)}
 LCS can take a value between 0 and
min(m,n)
.
Finally, let’s look at how we will calculate the LCS using the slideshow shown below:
Level up your interview prep. Join Educative to access 70+ handson prep courses.
Learn to code, grow your skills, and succeed in your tech interview