Longest common subsequence

O(m·n)

A subsequence keeps characters in order but lets you skip any of them; the longest common subsequence (LCS) is the longest one shared by both strings. The DP table dp[i][j] stores the LCS length of the first i characters of A and first j of B. When two characters match, the cell extends the diagonal by one; otherwise it takes the better of dropping a character from A or from B. Filling the table is O(m·n), and the bottom-right cell is the answer. LCS underlies diff, version control merges, and DNA sequence alignment.

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Fill the first row and column with 0 — any string against an empty one shares nothing.
  2. If the two characters match, take the diagonal value plus one.
  3. Otherwise take the larger of the cell above and the cell to the left.
  4. The bottom-right cell holds the length of the longest common subsequence.

Pseudocode

1lcs(a, b):                          # O(m·n)2  dp[i][0] ← 0,  dp[0][j] ← 0        # empty prefix → length 03  for i in 1..m, j in 1..n:4    if a[i-1] = b[j-1]:5      dp[i][j] ← dp[i-1][j-1] + 1    # extend the subsequence6    else:7      dp[i][j] ← max(dp[i-1][j], dp[i][j-1])8  return dp[m][n]