Solving LCS with Dynamic Programming

1. What is a Subsequence?

First, let's clarify the terminology. A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. For example, "ACE" is a subsequence of "ABCDE", but "AEC" is not.

The Longest Common Subsequence problem asks for the length of the longest subsequence that is common to two given strings.

2. The Recurrence Relation

As the video explained, we can define the problem recursively. Let LCS(X, Y) be the length of the longest common subsequence of strings X and Y. Let X_i be the prefix of X of length i, and Y_j be the prefix of Y of length j.

We can define dp[i][j] as the length of the LCS of X_i and Y_j. To find dp[i][j], we look at the last characters, X[i-1] and Y[j-1]:

1. If the characters match (X[i-1] == Y[j-1]):
   The LCS must include this character. The length is 1 plus the LCS of the strings without these last characters.

   $$dp[i][j]=1+dp[i-1][j-1]$$

2. If the characters do not match (X[i-1] != Y[j-1]):
   The LCS does not include both characters. We must discard one of them. We find the LCS by either discarding the last character of X or the last character of Y, and we take the longer of the two results.

   $$dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$$

These two rules, along with base cases dp[i][0] = 0 and dp[0][j] = 0 (LCS of any string with an empty string is 0), give us everything we need to solve the problem.

3. From Inefficient Recursion to Efficient DP

A naive recursive implementation of this logic would be incredibly slow, with a time complexity of $O(2^{m+n})$, because it repeatedly solves the same subproblems. This is the same issue we saw with the 0/1 Knapsack problem.

The solution, once again, is dynamic programming.

Memoization (Top-Down)

We can use our recursive function but add a 2D array (our memoization table) to cache the results of subproblems. Before computing LCS(X_i, Y_j), we check if the result is already in our table. If so, we return it; otherwise, we compute it, store it, and then return it.

Tabulation (Bottom-Up)

Alternatively, we can solve this iteratively. We create a 2D table of size (m+1) x (n+1) and fill it out starting from the base cases dp[0][0]. Each cell dp[i][j] is filled using the same recurrence relation, relying on values that have already been computed (dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]).

4. Implementation and Complexity

Now that you've seen the logic for both the top-down and bottom-up approaches, let's look at their implementation and formal complexity analysis.

As the article confirms, both DP approaches share the same complexity:

• Time Complexity: $O(m\times n)$, where m and n are the lengths of the two strings. We need to compute the value for each of the m x n cells in our DP table, and each computation takes constant time.
• Space Complexity: $O(m\times n)$ to store the DP table or the memoization cache.

5. Reconstructing the Actual Subsequence

Our DP table gives us the length of the LCS, but what if we want the subsequence itself? We can find it by backtracking through the filled table, starting from the last cell dp[m][n].

The logic is as follows:

1. Start at i = m, j = n.
2. If X[i-1] == Y[j-1], this character is part of the LCS. Prepend it to your result string and move diagonally up-left to (i-1, j-1).
3. If the characters don't match, compare dp[i-1][j] and dp[i][j-1].
   • If dp[i-1][j] > dp[i][j-1], move up to (i-1, j).
   • Otherwise, move left to (i, j-1). (If they are equal, you can choose either path; this means there are multiple longest common subsequences).
4. Repeat until i or j becomes 0.

6. Space Optimization

From an architectural perspective, it's always worth asking if we can optimize resource usage. To compute the values for the current row i of our DP table, we only need the values from the previous row, i-1. This means we don't need to store the entire m x n table in memory.

By using only one or two arrays of size n, we can reduce the space complexity to $O(n)$ (where n is the length of the shorter string), which is a significant improvement when dealing with very long strings.

Conclusion

Excellent work! You have successfully applied the dynamic programming framework to a second major problem. The thought process—identifying optimal substructure and overlapping subproblems, defining a recurrence, and then using memoization or tabulation—is a powerful and repeatable pattern.

Key Takeaways:

• The LCS problem seeks the longest ordered set of characters common to two strings.
• The core recurrence relation depends on whether the last characters of the prefixes match.
• Both top-down (memoization) and bottom-up (tabulation) DP approaches solve LCS in $O(m\times n)$ time and space.
• The actual subsequence string can be found by backtracking through the completed DP table.
• Space complexity can be optimized to $O(\min (m,n))$ by recognizing that only the previous row's results are needed for the current computation.

Preview of the Next Lesson:
In the next lesson, we will tackle the Edit Distance problem. You will be amazed at how similar it is to LCS. By making a small tweak to the recurrence relation we learned today, we can solve an entirely new problem, further cementing your understanding of the power and flexibility of dynamic programming.