Implementing Longest Common Subsequence (LCS) with Dynamic Programming

Hello! In our last lesson, we mastered the Unbounded Knapsack pattern, noting how a simple change in loop direction within a 1D DP array enabled us to solve a new class of problems like Coin Change.

Today, we shift gears from problems solvable with a 1D DP array to those that require comparing two sequences. This brings us to a foundational pattern in dynamic programming: the Longest Common Subsequence (LCS). Our goal is to derive the logic—the recurrence relation—that governs this problem and then implement it using a 2D DP table. This pattern is a cornerstone for solving many problems involving strings, arrays, and even genetics.

What is a Longest Common Subsequence?

Before we dive into the algorithm, let's be precise about what we're looking for. A "subsequence" is formed by deleting zero or more characters from a string while maintaining the relative order of the remaining characters. The "Longest Common Subsequence" of two strings is the longest possible subsequence that can be found in both of them.

From Recursion to Dynamic Programming

A natural way to approach LCS is to think recursively. For two strings, s1 and s2, we can compare their last characters. This leads to a decision tree of possibilities. While this recursive thinking helps identify the problem's structure, it's inefficient because it repeatedly solves the same subproblems. This is the classic signal that dynamic programming can be applied.

The key challenge, and the most important step in any DP problem, is defining the state. Since we are comparing two strings, our state must capture our progress through both of them. A single index is not enough. This naturally leads us to a 2D structure.

A fantastic article from Codeintuition lays out a systematic, three-step process for deriving any DP recurrence. We will use this process to build our LCS solution from the ground up.

Deriving the LCS Recurrence

Let's apply this three-step process to derive the recurrence for LCS. We are given two strings, let's call them text1 (length m) and text2 (length n).

Step 1: Define the State
Our state must capture the LCS of prefixes of both strings. Let's define dp[i][j] as "the length of the longest common subsequence between the prefix of text1 of length i (i.e., text1[0...i-1]) and the prefix of text2 of length j (i.e., text2[0...j-1])".

The dp table will therefore have dimensions (m+1) x (n+1).

Step 2: Derive the Transition
To compute dp[i][j], we look at the characters text1[i-1] and text2[j-1]. There are two possibilities:

1. The characters match: text1[i-1] == text2[j-1]
   If they match, this character can be part of our LCS. We have found a common character, so we can add 1 to the length of the LCS of the remaining prefixes (text1[0...i-2] and text2[0...j-2]).
   The recurrence is:
   $dp[i][j]=1+dp[i-1][j-1]$

2. The characters do not match: text1[i-1] != text2[j-1]
   If they don't match, we cannot use both characters. We must discard one of them. Our choice is to either:

   • Find the LCS of text1[0...i-2] and text2[0...j-1] (which corresponds to dp[i-1][j]).
   • Find the LCS of text1[0...i-1] and text2[0...j-2] (which corresponds to dp[i][j-1]).
     Since we want the longest common subsequence, we take the maximum of these two possibilities.
     The recurrence is:
     $dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$

Step 3: Set the Base Cases
The base cases handle the simplest scenarios. If one of the strings is empty, the LCS is 0. This means the first row and first column of our dp table, where either i=0 or j=0, should be all zeros.
$dp[i][0]=0\text{ for all }i$
$dp[0][j]=0\text{ for all }j$

The NeetCode video below provides an excellent visual walkthrough of this logic. It shows how these recurrence relations translate to movements in the 2D DP grid.

To solidify your understanding of the derivation itself, you can also read the step-by-step derivation in the Codeintuition article.

Implementing the Bottom-Up Solution

With the recurrence and base cases defined, we can now implement the solution by building the dp table from the ground up. We'll create an (m+1) x (n+1) grid, initialize it with zeros (which automatically handles our base cases), and then use nested loops to fill it according to our transition rules. The final answer will be the value in the bottom-right cell, dp[m][n].

Below is a Python implementation.

def longest_common_subsequence(text1: str, text2: str) -> int:
    m = len(text1)
    n = len(text2)
    



    # Create a DP table with dimensions (m+1) x (n+1)
    # The extra row and column handle the base cases (empty string)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    



    # Iterate through the strings to fill the DP table
    # Start from 1 because index 0 is for the empty string prefixes
    for i in range(1, m + 1):
        for j in range(1, n + 1):



            # Case 1: Characters match
            if text1[i-1] == text2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]



            # Case 2: Characters do not match
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                



    # The result is in the bottom-right corner of the table
    return dp[m][n]




# Example from the problem description
text1 = "abcde"
text2 = "ace"
print(f"LCS length for '{text1}' and '{text2}': {longest_common_subsequence(text1, text2)}") # Output: 3

text1 = "abc"
text2 = "def"
print(f"LCS length for '{text1}' and '{text2}': {longest_common_subsequence(text1, text2)}") # Output: 0

The image below shows a completed DP table for two sample strings. Each cell (i, j) contains the length of the LCS for the prefixes up to that point. The final answer, 3, is in the bottom-right cell.

For a line-by-line coding walkthrough, the final part of the NeetCode video is very helpful.

Conclusion

In this lesson, we transitioned from 1D DP problems to sequence-based 2D DP problems. By methodically defining the state, deriving the transition logic, and setting base cases, we built a robust solution for finding the Longest Common Subsequence.

Key Takeaways:

• 2D State for Two Sequences: When a problem involves comparing two sequences (like strings or arrays), the DP state often needs two dimensions, dp[i][j], to track progress in both.
• LCS Recurrence: The core of the LCS algorithm lies in two simple cases: if characters match, you add 1 to the diagonal dp[i-1][j-1]; if they don't, you take the maximum of the top dp[i-1][j] and left dp[i][j-1] cells.
• Bottom-Up Implementation: The recurrence relation is naturally implemented with a 2D table (a grid) that is filled iteratively, with the final solution appearing in the last cell.

The DP table we constructed holds more information than just the final length. The values in the table implicitly encode the path to construct the actual subsequence. In our next lesson, we will focus on exactly that: reconstructing the LCS string by tracing our steps backward through the completed table.