Longest Common Subsequence

Longest Common Subsequence is the classic introduction to two-dimensional dynamic programming. It teaches the move at the heart of dozens of string problems: build a grid where each cell answers a smaller version of the question, then read the answer off the corner.

The slow way first

The brute-force idea: generate every subsequence of s1 and check which ones also appear in s2. A string of length n has 2ⁿ subsequences, so this is exponential — hopeless for anything but tiny inputs.

The question to ask: what smaller problem would make this one easy? If I already knew the LCS length for shorter prefixes of both strings, I could extend it one character at a time. That is exactly what a DP table stores.

The idea: a grid of prefix answers

Let dp[i][j] be the LCS length of the first i characters of s1 and the first j characters of s2. The empty prefix shares nothing, so row 0 and column 0 are all 0. For every other cell, compare the two current characters:

If the characters match, this pair extends the LCS of the shorter prefixes: take the diagonal cell dp[i-1][j-1] and add 1. If they do not match, the best we can do is the better of dropping one character from either string: max(dp[i-1][j], dp[i][j-1]).

Walk through it

Step through the animation. The grid fills left to right, top to bottom. Watch the diagonal: whenever s1's row character equals s2's column character, the cell takes its diagonal neighbor plus one. Otherwise it copies the larger of the cell above or to the left. The final answer lands in the bottom-right cell, which lights up as 3.

Pseudocode

m, n = length of s1, length of s2
make a (m+1) x (n+1) grid "dp" filled with 0
for i from 1 to m:
    for j from 1 to n:
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1      # characters match: extend the diagonal
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])   # carry the best neighbor
return dp[m][n]                              # bottom-right cell is the answer

The Python solution

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

• dp is a grid with one extra row and column for the empty-prefix base case, all initialized to 0.
• The two loops fill every interior cell exactly once, in order, so each cell can safely read its already-computed neighbors.
• s1[i - 1] == s2[j - 1] compares the current characters — the - 1 is because row/column i/j correspond to the first i/j characters.
• On a match we add 1 to the diagonal dp[i - 1][j - 1], the answer for both prefixes shortened by one.
• On a mismatch we take max of the cell above and the cell to the left — the best LCS achievable by dropping one character.

Complexity

We fill an m × n table once, each cell in O(1), so the work is O(m × n). The space is the table itself; it can be reduced to O(n) by keeping only the previous row, but the full grid is clearer to reason about.

When this pattern shows up

Practice