Longest Common Subsequence

Start from brute force

The obvious approach is the recursion straight from the definition: compare the first characters; if they match, count 1 and recurse on both remainders, otherwise return the better of skipping a character of a or of b. It is correct, because an LCS either uses that matching pair or leaves out at least one of the two characters. Without memoization it costs O(2^(m+n)) time when nothing matches, since every call branches twice, plus O(m + n) stack. It is too slow because it solves the same pair of suffixes again and again: two 12-character strings with nothing in common already take 5,408,311 calls, and at 20 characters each it is about 276 billion.

The approach

The insight is that only the last characters of two prefixes matter. If a[i-1] == b[j-1], matching them is never worse, so the answer is one more than the LCS of both shorter prefixes. If they differ, at least one of them is not in the LCS, so the answer is the better of dropping one from a or one from b. There are only (m + 1)(n + 1) prefix pairs, so compute each once and look it up.

The reference allocates dp as (m + 1) × (n + 1) zeros, where dp[i][j] is the LCS of a[:i] and b[:j]; row 0 and column 0 are the empty prefixes. It fills rows top to bottom and columns left to right, which is the invariant that makes it work: when cell (i, j) is computed, the cells above, to the left and diagonally up-left are already final. A match sets dp[i][j] = dp[i - 1][j - 1] + 1; a mismatch sets max(dp[i - 1][j], dp[i][j - 1]). The answer is dp[m][n].

Walk through an example

The first example, a = "abcde" and b = "ace", one table row per character of a; the bottom-right cell is the answer.

Complexity

DP: O(m·n) time, one constant-time cell per pair of prefixes, and O(m·n) space for dp; keeping only two rows cuts that to O(min(m, n)) when only the length is needed. Brute force: the plain recursion is O(2^(m+n)) time when nothing matches, because every call branches twice, with O(m + n) stack depth.

Edge cases to test

• Either string empty: lcs("", "anything") is 0, read straight from the zero row of dp.
• Same letters in a different order: lcs("abc", "cba") is 1, not 3. Counting shared characters ignores order and over-counts.
• Repeated characters: lcs("aaaa", "aa") is 2, because each position can be matched only once.
• Greedy matching fails on a = "aba", b = "bac": matching the first a as early as possible leaves nothing usable after it and gives 1, while the answer is 2 ("ba").
• Case matters: lcs("ABC", "abc") is 0, since characters compare exactly.

Common mistakes

• Confusing subsequence (not contiguous) with substring (contiguous) — different problems.
• Getting the mismatch recurrence wrong (it is the max of the two “drop one” options).
• Indexing the strings with the table indices: row i of dp stands for the first i characters, so it compares a[i - 1], not a[i].
• Matching greedily, taking each character of a at its earliest position in b: "aba" against "bac" gives 1 instead of 2.

Follow-ups an interviewer asks next

Return the subsequence itself, not just its length.

Keep the full table and walk back from dp[m][n]: when a[i-1] == b[j-1], that character is in the answer, so record it and step diagonally; otherwise step toward the larger of dp[i-1][j] and dp[i][j-1]. Reverse the collected characters at the end. The walk is O(m + n) after the O(m·n) fill, and returns "ace" for the first example.

Both strings have 100,000 characters.

The full table would have about 10^10 cells, far too much memory. For the length alone, keep only the previous and current rows, O(min(m, n)) space, because each cell reads only the row above and the cell to its left. To recover the subsequence in linear space too, Hirschberg’s algorithm splits a in half, finds where the optimal path crosses the middle row with two linear-space passes, and recurses, still in O(m·n) time.

Turn it into a line-based diff of two files.

Treat each line as one symbol, usually by hashing lines to integers so comparisons are cheap. Lines in the LCS are unchanged; lines of the old file outside it are deletions and lines of the new file outside it are insertions. Diff tools also avoid the full table: Myers’ algorithm runs in O((m + n) · D) time, where D is the size of the edit, which is fast for files that differ a little.

How does it relate to edit distance?

If the only edits allowed are inserting and deleting characters, the minimum number of edits is m + n - 2 · lcs(a, b): delete everything in a outside the LCS and insert everything in b outside it. For "abcde" and "ace" that is 5 + 3 − 6 = 2. Allowing substitutions too gives Levenshtein distance, which fills the same table shape with a different recurrence.

Where this shows up

LCS is the core of diff tools — git diff and file comparison find the longest common subsequence, and everything not in it is an insertion or deletion. The same DP underlies version control, DNA sequence alignment, and the whole edit-distance family.

Reference solution

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # dp[i][j] = LCS(a[:i], b[:j])
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1   # match: extend the diagonal
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # drop one char
    return dp[m][n]


print(lcs("abcde", "ace"))       # -> 3
print(lcs("aggtab", "gxtxayb"))  # -> 4

function lcs(a: string, b: string): number {
  const m = a.length, n = b.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 (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;  // match
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);        // drop one
    }
  }
  return dp[m][n];
}

console.log(lcs("abcde", "ace"));      // -> 3
console.log(lcs("aggtab", "gxtxayb")); // -> 4