Easy Problemsstringoptimization

Longest Common Substring

Given two strings, find the length of their longest common substring: a run of characters that must appear contiguously, in the same order, within both strings.

Do this lesson first: longest common subsequence

Example input

A = "XABCDEZ", B = "BCYXABCDAZ"

Expected output

5

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 substring that ENDS exactly at A's i-th letter and B's j-th letter: the longest run of letters that A's first i letters and B's first j letters both finish with. Here m = 7 is A's length and n is how many letters of B the slider takes, 10 at the drive size. Row i's own letter is A[i - 1] and column j's is B[j - 1], which is why row 5's gutter reads 5 D. Pinning the run's END at both i and j is the whole insight. The cell on the longest-common-subsequence page holds the best answer found anywhere within the two prefixes, so it can lean on a neighbour that found a good answer earlier. This cell cannot, because a run that ends here is either glued to the run ending one letter back on both strings or it does not exist. dp[5][8] = 5 says that the five letters ending at A's D and at B's D agree, XABCD in both, and it says nothing about any run that ends somewhere else.

dp[i][j] = dp[i - 1][j - 1] + 1 if A[i - 1] = B[j - 1], else 0

A common substring that ends at this pair has to use both last letters, A[i - 1] and B[j - 1], since it ends exactly on them. So there is no choice to make here, only a test. If the two letters differ, no run ends on this pair at any length, and the cell is 0. If they match, the run is this pair plus whatever run ended one letter earlier in both strings, dp[i - 1][j - 1], and nothing else. The cell above ends its run on the same letter of B that this pair uses, and the cell to the left ends on the same letter of A, so this pair cannot extend either of them; only the diagonal stops one letter short in both. Hold that against LCS. A subsequence may skip letters, so LCS's mismatch branch drops the last letter of one string and keeps max(dp[i - 1][j], dp[i][j - 1]). A substring may not skip anything, so the same mismatch here resets the cell to 0.

Row 0 and column 0 are given as 0, because no run can end on a pair where one of the two prefixes is empty: that side has no letter to pair with. At the drive size that is 18 bases: 11 across row 0 for columns 0 to 10, and 7 more down column 0 for rows 1 to 7. A computed cell reads at most one cell, the diagonal up and to the left, and a row-major sweep, left to right within each row, has always finished it, since the sweep completed the whole previous row first. A mismatch reads nothing at all. THE RESET IS WHY THE ANSWER IS A SCAN. On the LCS page no cell is ever smaller than the cell above it or the cell to its left, so the last cell holds the answer. Here a mismatch drops a cell to 0 however long the run beside it, so the last cell reports only on the run that ends at both strings' final letters: dp[7][10] = 1, the shared Z, against the answer 5 at dp[5][8]. At lengths 6 to 9 the last cell holds 0. The answer is the largest cell anywhere in the table, so a running best has to travel with the sweep.

Tabulation over all (m + 1) × (n + 1) cells. At the drive size 70 cells are computed, and 61 of them are mismatches that read nothing and write 0. A memoized top-down solve saves nothing here. On the LCS page it can skip cells, since one call from dp[m][n] follows only the branches it needs; this answer is the largest cell anywhere, so every cell is a candidate and has to be asked about. Space is where this table is cheaper than LCS's. A cell reads only its diagonal, so the table falls apart into m + n - 1 independent diagonals, 16 at the drive size, and a single counter that walks one diagonal at a time and resets on each mismatch reproduces every cell in O(1) space. One row swept right to left works too, since dp[i - 1][j - 1] is still the previous row's value when j comes down to it. Drag the slider and B grows one letter at a time while A stays put; the answer goes 3, 4, 5, 5, 5 across lengths 6 to 10. At length 6, B ends on X, A, B, and the run XAB fills dp[3][6] = 3. The C at length 7 and the D at length 8 each extend that same run by one letter, to dp[4][7] = 4 and dp[5][8] = 5, so the answer cell walks down one diagonal. The A at length 9 lands against A's E on that diagonal, a mismatch, and the run stops at 5. The Z at length 10 does match A's last letter, but the pair before it is E against A, so it opens a new run of 1 and the answer stays 5.

Time O(m × n)Space O(m × n), reducible to O(n) with one row swept right to left, or O(1) by walking each diagonal with a counter

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 no run can end on a pair where one of the two prefixes is empty: that side has no letter to pair with. At the drive size that is 18 bases: 11 across row 0 for columns 0 to 10, and 7 more down column 0 for rows 1 to 7. A computed cell reads at most one cell, the diagonal up and to the left, and a row-major sweep, left to right within each row, has always finished it, since the sweep completed the whole previous row first. A mismatch reads nothing at all. THE RESET IS WHY THE ANSWER IS A SCAN. On the LCS page no cell is ever smaller than the cell above it or the cell to its left, so the last cell holds the answer. Here a mismatch drops a cell to 0 however long the run beside it, so the last cell reports only on the run that ends at both strings' final letters: dp[7][10] = 1, the shared Z, against the answer 5 at dp[5][8]. At lengths 6 to 9 the last cell holds 0. The answer is the largest cell anywhere in the table, so a running best has to travel with the sweep.

Rows ↓
Cols →

∅

1 B

2 C

3 Y

4 X

5 A

6 B

7 C

8 D

9 A

10 Z

∅

0

1 X

0

1

0

2 A

0

2

0

1

0

3 B

0

1

0

3

0

4 C

0

2

0

4

0

5 D

0

5

0

6 E

0

7 Z

0

1

Rows ↓A: XABCDEZ

Cols →B: the first n letters of BCYXABCDAZ

longest-common-substring.ts

1function longestCommonSubstring(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 let best = 0;
5 for (let i = 1; i <= m; i++) {
6 for (let j = 1; j <= n; j++) {
7 dp[i][j] = a[i - 1] === b[j - 1]
8 ? dp[i - 1][j - 1] + 1
9 : 0;
10 best = Math.max(best, dp[i][j]);
11 }
12 }
13 return best;
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-common-substring.ts

1function longestCommonSubstring(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 let best = 0;
5 for (let i = 1; i <= m; i++) {
6 for (let j = 1; j <= n; j++) {
7 dp[i][j] = a[i - 1] === b[j - 1]
8 ? dp[i - 1][j - 1] + 1
9 : 0;
10 best = Math.max(best, dp[i][j]);
11 }
12 }
13 return best;
14}

Where people go wrong

Carrying LCS's mismatch rule over: writing max(dp[i - 1][j], dp[i][j - 1]) where this page writes 0. The table that rule builds is the LCS table, and on this pair it hides well. Read as its last cell or as its largest cell, which is the same number in that table, it returns 3, 4, 5, 5 at lengths 6 to 9, right at every one, because up to length 9 the longest common subsequence of these strings happens to be contiguous. At length 10 it returns 6, for XABCDZ, which is not a substring of either string: in A an E sits between the D and the Z, and in B an A does. One slider position in five catches it, so test on an input where the subsequence and the substring differ. The second trap is LCS's other habit, returning dp[m][n]; here that gives 0, 0, 0, 0, 1 across the five lengths, wrong at every one.

Return the longest common substring itself, not just its length.
The table, its recurrence and its bases do not change; the running best also records WHERE it was found, the cell (i, j). A run is contiguous, so its end and its length pin it completely: the answer is A's letters i - best + 1 to i, which are also B's letters j - best + 1 to j. Here that is the cell (5, 8) with length 5, A's letters 1 to 5, XABCD. No walk back through the table is needed, unlike LCS, where a subsequence's letters are scattered and have to be recovered one step at a time, so the O(1) diagonal sweep from the execution panel still works. A tie needs a rule. With B's first 5 letters, below this slider's range, dp[2][5] (XA) and dp[4][2] (BC) both reach 2; keeping the first maximum in row-major order prints XA, and keeping the last prints BC.
Allow up to k mismatched positions: the longest pair of equal-length substrings, one from each string, that differ in at most k places.
The state gains a third index, t from 0 to k, the most mismatches the run may contain: dp[i][j][t] is the longest such run ending at A's i-th and B's j-th letter with at most t mismatches. A match still extends the diagonal, dp[i - 1][j - 1][t] + 1. A mismatch no longer forces 0: with t > 0 it spends one and extends dp[i - 1][j - 1][t - 1] + 1, and only at t = 0 is it the reset this page performs. The bases do not change: row 0 and column 0 are 0 at every t, since no run can end on a pair with an empty prefix however many mismatches it may spend. The t = 0 layer is exactly this page's table, the sweep stays row-major, and the cost grows to O(m × n × (k + 1)). On this pair, k = 1 lifts the answer from 5 to 7: all of A, XABCDEZ, against B's last seven letters, XABCDAZ, which differ only where A has its E and B has an A.

Jump Game Count all paths in a Grid