Longest Common Subsequence

How it works, step by step

1. 1

   Write one string down the side and the other across the top. Add an extra ∅ row and column: against an empty prefix, the answer is 0.

2. 2

   Each cell asks one small question: how long is the LCS of the row-prefix and the column-prefix that end here?

3. 3

   If the two letters match, take the diagonal neighbour and add 1 - this match extends the best answer that ignored both letters.

4. 4

   If they differ, copy the bigger of the cell above and the cell to the left - drop the last letter of one string or the other, and keep the better result.

5. 5

   Fill the table row by row. The bottom-right cell holds the LCS length.

6. 6

   For the string itself, walk back from that corner: every diagonal step is a matched letter. Read them in reverse.

The code, in JavaScript

function lcsLength(a, b) {
  const n = a.length, m = b.length;

  // dp[i][j] = LCS length of a's first i letters and b's first j letters.
  // Row 0 and column 0 stay 0: against an empty string, nothing is shared.
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (a[i - 1] === b[j - 1]) {
        // Match: extend the best answer that used neither letter.
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // No match: drop the last letter of one string or the other.
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[n][m];                  // bottom-right corner = the answer
}

lcsLength("REACT", "TRACE");      // → 3  (they share "RAC")
lcsLength("SUNDAY", "SATURDAY");  // → 5  (they share "SUDAY")

Dry run: the LCS of "REACT" and "TRACE"

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Subsequence is not substring: gaps are allowed. "RAC" is not a substring of "REACT" (the E sits in the middle), yet it is a perfectly valid subsequence. Solving the wrong one of the two is a classic interview miss.
• The length is unique, the string is not: when up and left tie, both choices are valid but lead to different subsequences. `>=` vs `>` in the traceback silently changes which answer you return - decide deliberately if the caller cares.
• The two-row memory trick keeps the length but destroys the traceback - you cannot recover the string from two rows. Hirschberg's divide-and-conquer gets both, O(m) memory *and* the string, at the cost of trickier code.
• O(n·m) memory blows up fast: two 100k-character documents want 10 billion cells. Production diffs (git included) use Myers' O(n·d) algorithm, which only does work proportional to how *different* the files are.

Longest Common Subsequence vs. its closest relatives