Longest Common Subsequence

Fill for the optimal length, then trace for an actual subsequence

Preserve order without requiring adjacency

A subsequence keeps the original character order but may skip characters. For prefixes of strings X and Y, let dp[i][j] be their longest common subsequence length. Empty prefixes form the zero row and column.

Match diagonally or discard one character

When X[i - 1] === Y[j - 1], append that shared character to the best solution for the shorter prefixes, giving the top-left value plus 1. Otherwise one current character must be skipped, so keep the larger value from the up and left cells.

After the table is full, the player traces backward from the bottom-right cell. A character match moves diagonally and records that character; a mismatch follows a neighboring cell that preserves the optimal length. The highlighted path reconstructs ACD.

	A	C	D	F
∅	0	0	0	0
A
B
C
D

Initialize the empty-prefix row and column to 0.

1function lcs(x: string, y: string): string {
const m = x.length, n = y.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (x[i - 1] === y[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; // equal: top-left + 1
    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);       // different: max of up/left
  }
}
let i = m, j = n, s = "";
while (i > 0 && j > 0) {                        // reconstruct the LCS
  if (x[i - 1] === y[j - 1]) { s = x[i - 1] + s; i--; j--; }    // take the character and move diagonally
  else if (dp[i - 1][j] >= dp[i][j - 1]) i--;   // follow the larger up/left value
  else j--;
}
return s;
17}

String XABCD

String YACDF

1 / 24

Value first, witness second

The table takes O(mn) time and space. This two-phase pattern appears throughout dynamic programming: first compute the optimal value, then follow stored choices to recover a concrete solution.

LCS underlies sequence comparison and diff tools. A common subsequence need not be contiguous, which distinguishes it from a common substring.

Contrast this maximum-length recurrence with Edit Distance, or continue to a one-dimensional subsequence DP in Longest Increasing Subsequence.

Algorithm Visualizer

Longest Common Subsequence

Preserve order without requiring adjacency

Match diagonally or discard one character

Value first, witness second