Medium Problemsstringoptimization

Longest Common Subsequence

Given two strings, find the length of their longest common subsequence: characters that appear in both strings in the same relative order, though not necessarily next to each other.

Do this lesson first: longest common subsequence

Example input

A = "ABCBDAB", B = "BDCABA"

Expected output

4

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is the length of the longest common subsequence of A's first i letters and B's first j letters. Two numbers name the state, one prefix length per string, so with m = |A| and n = |B| the table is an (m + 1) × (n + 1) grid, one extra row and one extra column for the empty prefixes. Row i's own letter is A[i - 1] and column j's is B[j - 1], which is why row 3's gutter reads 3 C: the 3 is the dp index and the C is the letter that row adds. The cell holds a length and nothing about which letters achieved it.

dp[i][j] = dp[i - 1][j - 1] + 1 if A[i - 1] = B[j - 1], else max(dp[i - 1][j], dp[i][j - 1])

The full derivation, why a matching last pair can be taken together at no risk and why a mismatch has to drop the last letter of one string or the other, lives in the flagship lesson at /courses/dynamic-programming/longest-common-subsequence. This page assumes it and goes straight to the table.

Row 0 and column 0 are given as 0, because an empty prefix shares nothing with any prefix of the other string. At the drive size that is 14 bases: 7 across row 0 for columns 0 to 6, and 7 more down column 0 for rows 1 to 7. Every interior cell reads only cells above it, to its left, or diagonally above-left, so a row-major sweep, left to right within each row, has finished all three before any of them is needed. The diagonal costs nothing extra: the sweep completed the whole previous row before it started this one.

Tabulation over all (m + 1) × (n + 1) cells, where m = |A| and n = |B|. A memoized top-down solve would skip some of them: from dp[7][6] on this pair it reaches 25 of the 42 interior cells, because a match sends the recursion down one diagonal and never looks at the cells beside it. Tabulation is still the usual choice, since it needs no call stack and its row-by-row order means a cell reads only the row above and its own row, so two rolling rows of n + 1 cells are enough (put the shorter string across the top). Drag the slider and B grows one letter at a time while A stays put; the answer goes 3, 4, 4, 4, 4, 5, 5 across lengths 4 to 10. It moves twice. At length 5, B gains a B, and the 3-letter answers BCA and BDA each gain a closing B. At length 9, B gains another B, and BCBD and BCBA each gain one too. The A, D and C that arrive at lengths 6, 7 and 8 leave the answer at 4, and the A at length 10 leaves it at 5. A new letter of B can raise the answer by at most 1, and does so exactly when it extends one of the current best answers.

Time O(m × n) for |A| = m and |B| = nSpace O(m × n), reducible to O(min(m, n)) with two rolling rows

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 and column 0 are given as 0, because an empty prefix shares nothing with any prefix of the other string. At the drive size that is 14 bases: 7 across row 0 for columns 0 to 6, and 7 more down column 0 for rows 1 to 7. Every interior cell reads only cells above it, to its left, or diagonally above-left, so a row-major sweep, left to right within each row, has finished all three before any of them is needed. The diagonal costs nothing extra: the sweep completed the whole previous row before it started this one.

Rows ↓
Cols →

∅

1 B

2 D

3 C

4 A

5 B

6 A

∅

0

1 A

0

1

2 B

0

1

2

3 C

0

1

2

4 B

0

1

2

3

5 D

0

1

2

3

6 A

0

1

2

3

4

7 B

0

1

2

3

4

Rows ↓A: ABCBDAB

Cols →B: the first n letters of BDCABADCBA

longest-common-subsequence.ts

1function lcs(a, b) {
2 const m = a.length, n = b.length;
3 const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
4 for (let i = 1; i <= m; i++) {
5 for (let j = 1; j <= n; j++) {
6 const match = a[i - 1] === b[j - 1];
7 dp[i][j] = match
8 ? dp[i - 1][j - 1] + 1
9 : Math.max(dp[i - 1][j], dp[i][j - 1]);
10 }
11 }
12 return dp[m][n];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-common-subsequence.ts

1function lcs(a, b) {
2 const m = a.length, n = b.length;
3 const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
4 for (let i = 1; i <= m; i++) {
5 for (let j = 1; j <= n; j++) {
6 const match = a[i - 1] === b[j - 1];
7 dp[i][j] = match
8 ? dp[i - 1][j - 1] + 1
9 : Math.max(dp[i - 1][j], dp[i][j - 1]);
10 }
11 }
12 return dp[m][n];
13}

Where people go wrong

Adding 1 to the wrong cell on a match. The match branch reads the DIAGONAL, dp[i - 1][j - 1], because pairing the two letters uses both of them up. Writing max(dp[i - 1][j], dp[i][j - 1]) + 1 instead looks like a harmless generalisation, and on this pair it first goes wrong at dp[1][6]. That cell pairs A's first letter, an A, with B's sixth letter, also an A. Its left neighbour dp[1][5] = 1 already spends that same A, matched against B's fourth letter, so max(0, 1) + 1 writes 2 and claims a two-letter common subsequence from a one-letter prefix of A. The diagonal dp[0][5] = 0 is the honest starting point and gives 1. The error compounds from there: the wrong rule finishes this table at 5 instead of 4.

Print one longest common subsequence, not just its length.
The table and its recurrence do not change; a second pass walks back through the finished table from dp[m][n]. On a match, step diagonally and keep the letter; on a mismatch, step toward the larger neighbour; stop at row 0 or column 0 and read the kept letters in reverse. The walk is at most m + n steps and computes no new cell. Its one real choice is a tie, and the tie decides which answer you print: on this pair, the walk from dp[7][6] spells BCBA when ties step up and BDAB when ties step left. The simple walk needs the whole table, so the two-rolling-row saving from the execution panel does not carry over.
Find the length of the shortest common supersequence: the shortest string that contains both A and B as subsequences.
Same table, same recurrence, one subtraction at the end: |A| + |B| - LCS, because every letter of the common subsequence is written once instead of twice and every other letter has to appear. On this pair that is 7 + 6 - 4 = 9. Building the string itself is the walk-back from the variation above, writing the shared letter once on a match, the dropped letter on each mismatch step, and whatever prefix remains when the walk reaches an edge.
Count the fewest single-letter insertions and deletions that turn A into B.
Still the same table: keep the common subsequence, delete the rest of A, insert the rest of B, so the count is |A| + |B| - 2 × LCS, which is 7 + 6 - 8 = 5 on this pair. Allow a third operation, replacing one letter with another, and that shortcut breaks, because one replacement can stand in for a deletion plus an insertion. The recurrence changes shape: a mismatch costs 1 plus the smallest of three neighbours, the diagonal now standing for a replacement, and the table counts edits to minimize rather than shared letters to maximize. The edges change too, from zeros to dp[i][0] = i and dp[0][j] = j, because turning a prefix into the empty string, or the empty string into a prefix, takes one edit per letter. That is the edit-distance page.

Water Overflow Longest Increasing Subsequence