Longest Common Subsequence

Find the longest run of letters two strings share in order by filling a prefix-by-prefix grid — O(m·n).

The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both, in the same order, but not necessarily next to each other. For ABCBDAB and BDCAB the answer is BCAB (length 4). Note the difference from a *substring*: a subsequence may have gaps. LCS is the engine behind diff, version-control merges, and DNA alignment.

The grid: every prefix against every prefix

Build a table dp[i][j] = the LCS length using the first `i` letters of string `X` and the first `j` letters of string `Y`. Row 0 and column 0 are all zeros (an empty prefix shares nothing). Then fill the grid top-to-bottom, left-to-right, where each cell looks only at three already-solved neighbours: the one above, the one to the left, and the one diagonally up-left.

1If the current letters match (X[i] === Y[j]): extend the diagonal run — dp[i][j] = dp[i-1][j-1] + 1.
2If they differ: you must drop one letter, so inherit the better of the two options — dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3The bottom-right cell dp[m][n] holds the final LCS length.
4Trace back from that corner to recover the actual subsequence (optional).

Why a match steps diagonally

A matching letter belongs in the LCS, so you consume *one* letter from each string and add 1 to the best answer for the *shorter* prefixes — that smaller answer lives exactly one cell up-and-to-the-left.

X = AGCAT   Y = GAC          dp grid (rows X, cols Y)
        ""  G  A  C
   ""    0  0  0  0
    A    0  0  1  1
    G    0  1  1  1
    C    0  1  1  2
    A    0  1  2  2
    T    0  1  2  2   <- LCS length = 2 ("AC" or "GA")

function lcs(X, Y) {
  const m = X.length, n = Y.length;
  const dp = Array.from({ length: m + 1 }, () => new 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;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}

Length needs only two rows

Each cell depends only on the current and previous row, so if you want just the *length* you can keep two rows and drop space to O(min(m, n)). You need the full grid only to trace the actual subsequence back out.

OperationTimeSpace

Fill the grid · one pass, each cell O(1)O(m·n)O(m·n)

Length only · rolling two rowsO(m·n)O(min(m,n))

Check yourself

When the two current letters differ, what does an LCS cell store?