Dynamic Programming for Longest Common Subsequence

Welcome back! In our last lesson, we explored the 0/1 dynamic programming pattern to solve the subset sum problem. You learned how to define a state that answers a "yes/no" question and formulate a transition based on a "take-it-or-leave-it" choice.

Today, we'll conclude our module on dynamic programming by tackling another classic problem that's a staple in technical interviews: finding the longest common subsequence. Our learning outcome is to compute the longest common subsequence of two strings with two-dimensional dynamic programming. This pattern is essential for problems that involve comparing two sequences, whether they are strings, arrays, or other ordered data. It builds directly on your understanding of 2D DP tables but introduces a new kind of state and transition.

What is a Subsequence?

First, let's be precise about our terms. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, "ace" is a subsequence of "abcde" because you can obtain "ace" by deleting 'b' and 'd'. However, "aec" is not a subsequence of "abcde" because the 'e' and 'c' are out of order.

The Longest Common Subsequence (LCS) problem asks for the length of the longest subsequence that is common to two given strings. For text1 = "abcde" and text2 = "ace", the LCS is "ace", and its length is 3.

Devising a Recursive Solution

As with many DP problems, we can start by thinking recursively. How can we break the problem of finding LCS(text1, text2) into smaller, similar subproblems? A powerful strategy is to make a decision based on the characters at the ends of the strings.

Let's say s1 has length m and s2 has length n. We'll compare their last characters, s1[m-1] and s2[n-1].

1. Case 1: The last characters match.
   If s1[m-1] == s2[n-1], then this character must be part of the LCS. We can "claim" this matching character and add it to our subsequence. The length of our LCS is now 1 plus the LCS of the remaining parts of the strings: LCS(s1[0..m-2], s2[0..n-2]).

2. Case 2: The last characters do not match.
   If s1[m-1] != s2[n-1], they can't both be the last character of our common subsequence. We have to discard one of them. This gives us two possibilities, and we must take the one that yields a longer result:

   • Either we discard the last character of s1 and find the LCS(s1[0..m-2], s2[0..n-1]).
   • Or we discard the last character of s2 and find the LCS(s1[0..m-1], s2[0..n-2]).
     The answer is the max of these two subproblems.

This recursive logic defines the problem perfectly, but it's inefficient. As shown in the diagram below, trying to find the LCS of "AXYT" and "AYZX" leads to re-computing L("AXY", "AYZ") multiple times. This overlapping subproblem structure is our cue to use dynamic programming.

From Recursion to 2D Dynamic Programming

We can turn our recursive solution into an efficient bottom-up DP algorithm. The state of our recursive calls was defined by the lengths of the string prefixes we were considering. This maps perfectly to a 2D array.

State: Let dp[i][j] be the length of the longest common subsequence between the first i characters of text1 (i.e., text1.slice(0, i)) and the first j characters of text2 (i.e., text2.slice(0, j)).

Our DP table will have dimensions (m+1) x (n+1), where m and n are the lengths of text1 and text2. The extra row and column handle the base cases where one of the strings is empty.

Base Cases: If one string is empty, the LCS is 0. So, dp[i][0] = 0 for all i and dp[0][j] = 0 for all j. Initializing our table with zeros takes care of this automatically.

Transition: The transition logic directly follows our recursive cases. To compute dp[i][j], we compare text1[i-1] and text2[j-1] (note the index shift from 1-based DP table to 0-based strings):

• If text1[i-1] == text2[j-1]: The characters match. We extend the LCS from the smaller subproblem.
  $dp[i][j]=1+dp[i-1][j-1]$
• If text1[i-1] != text2[j-1]: The characters don't match. We take the best result from the two possible subproblems.
  $dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$

The final answer to our problem will be the value in the bottom-right corner of the table, dp[m][n].

Visualizing the Algorithm

The best way to understand how this table gets filled is to see it in action. The NeetCode video you started earlier provides an excellent walkthrough. It uses a slightly different visualization (working from bottom-right to top-left), but the core logic is identical. Pay close attention to the two rules: what to do when characters match, and what to do when they don't.

After filling the table, you get a matrix of numbers where the final answer is at the bottom right. The image below shows a completed DP table for text1 = "ACBDA" and text2 = "ABCDA". The numbers in the cells represent the lengths of the LCS for the corresponding prefixes. The red path traces back how the LCS "ACDA" (length 4) was constructed.

Implementation and Key Details

Now, let's look at a complete implementation and consolidate the details. The following resource provides a clear, step-by-step guide with code.

As a quick note on optimization, you might notice that to compute any cell dp[i][j], you only need values from the previous row (i-1) and the current row (i). Just like with the subset sum problem, this means the space complexity can be optimized from $O(m\times n)$ down to $O(n)$ (the length of the shorter string). The GeeksForGeeks article provides a good explanation of this space optimization, which you can explore if you're curious.

Conclusion

Congratulations on completing the final lesson of our Dynamic Programming module! You have now mastered three fundamental DP patterns: path-finding on grids, 0/1 subset problems, and now, comparing sequences with LCS.

Here are the key takeaways for the Longest Common Subsequence pattern:

• Problem Recognition: Look for problems that ask to compare two sequences (strings, arrays) to find a longest commonality while preserving order.
• State Definition: The state dp[i][j] almost always represents the answer for the prefixes of length i and j of the two sequences.
• Transition Logic: The core of the algorithm lies in two cases:
  • If text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1] (extend the diagonal).
  • If text1[i-1] != text2[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the best of excluding from one or the other).
• Complexity: The standard 2D DP solution has a time and space complexity of $O(m\times n)$.

With these core DP patterns under your belt, you are well-equipped to recognize and solve a large variety of dynamic programming problems.

In our next module, "High-Value Advanced Interview Patterns," we will shift gears to cover a curated set of other powerful techniques and data structures frequently seen in interviews, such as Quickselect, Tries, and monotonic deques.