Longest Common Subsequence

Find the length of the longest common subsequence between two strings.

Pattern fit

This is the canonical sequence DP because the state depends on prefixes of two strings and whether the current characters match.

Key observation

If the characters match, you take the diagonal; otherwise you inherit the better of skipping one character from either side.

Target complexity

O(mn) / O(mn)

How to break down the solution cleanly

This is the canonical sequence DP because the state depends on prefixes of two strings and whether the current characters match.

If the characters match, you take the diagonal; otherwise you inherit the better of skipping one character from either side.

Name the state in plain language.

List the decisions that can transition into the state.

Reference implementation

Python

# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
    dp[i] = transition(dp, i)

# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = transition(dp, i, j)

Common pitfalls

warning

Using substring intuition instead of subsequence intuition.

warning

Writing transitions that skip both characters at once unnecessarily.

Common follow-ups

How would you reconstruct one actual subsequence?

How does edit distance relate to this state grid?

Continue with related problems

Build repeatable depth inside the Dynamic Programming cluster before moving on.

view_weekBack to the pattern page