Longest Common Subsequence's own opening
paragraph picks two strings, "ABCBDAB" and "BDCABA", that "don't share a long
unbroken run anywhere" but do share "BCBA" if characters are allowed to skip around. This
entry asks the question that sentence sets aside: what's the longest run those same two strings
do share without skipping anything — a genuinely contiguous, unbroken block
that appears in both, letter for letter, back to back? The two problems sound like small variations on
each other, and the table they're solved with looks almost identical, but the actual answers are not
close: those two strings' longest common subsequence is 4 characters long
("BCBA"); their longest common substring is only 2
("AB" — it shows up twice, and a third contiguous run, "BD", ties it, more on
that in Pitfalls). Contiguity is a real constraint, not a cosmetic one, and it
changes more than the answer: it changes where in the table the answer even lives.
Same two strings as Longest Common Subsequence's own demo, A = "ABCBDAB" and
B = "BDCABA", so the two pages' tables can be compared side by side. Press
Step or Run to fill dp[i][j] one cell at a time: on a
match it extends the diagonal run by one, same as Longest Common Subsequence; on a mismatch it resets
straight to 0 instead of carrying forward the better neighbor, because a substring that
skips a character stops being contiguous. The demo tracks the single highest value seen anywhere in the
table so far — highlighted in a different color from the cell currently being filled — and updates it
live. There's no backtracking phase: the moment a new high is set, the actual substring is already fully
determined (it's just the maxLen characters of A ending at the current row), so
it's read off directly instead of walked back through afterward.
Switch the mode dropdown to bug: carry forward like LCS to run the exact mismatch rule
Longest Common Subsequence uses (max(dp[i-1][j], dp[i][j-1])) instead of resetting to 0, while
still reporting the table's global maximum as "the answer." Watch the reported length climb past the real
answer of 2 and land on 4 — not a slightly-off number, but the exact length of the two
strings' longest common subsequence, because that's genuinely what this mismatch rule computes,
regardless of which problem it's being asked to solve.
The recurrence has the same two cases as every other two-sequence table on this site, but the
mismatch case is forced to a different answer by what "substring" means. On a match,
A[i-1] === B[j-1], extending the diagonal run is still always correct for the same reason
Longest Common Subsequence extends it: a shared character can never hurt, so
dp[i][j] = dp[i-1][j-1] + 1. On a mismatch, Longest Common Subsequence carries
forward the better of its two neighbors, because a subsequence is still free to skip the character that
didn't match and keep going. A substring has no such freedom — the moment two characters at position
i, j disagree, any run that was ending here is over. It cannot continue as some other, still
contiguous run of the same length borrowed from a neighboring cell, because that borrowed run would, by
definition, not include position i, j — so dp[i][j] must drop to exactly
0, not the best of its neighbors.
That one-word difference in the mismatch rule has a consequence that reaches past the recurrence
itself: it breaks the convention every other entry on this site's Dynamic Programming guide relies on,
that the final answer sits in the bottom-right corner, dp[m][n]. Longest Common Subsequence
and Edit Distance can both read their answer from that one
cell because their tables accumulate monotonically toward it — every cell is at least as good as the
ones that could feed into a worse answer. This table does the opposite on purpose: it actively resets to
zero, over and over, at every mismatch. The longest run can end anywhere in the middle of either string,
with nothing but zeros between it and the corner. The only way to find it is to track the single largest
value seen across every cell, the whole time the table fills — which is exactly why this demo
keeps a running "best so far" instead of only rendering the finished grid.
Builds the same-shaped table as Longest Common Subsequence, but resets to 0 on a mismatch and tracks
the best cell seen instead of reading the corner. No backtracking step: the substring is a direct slice
of a, read off the moment a new best is recorded.
function longestCommonSubstring(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
let maxLen = 0, endIndexInA = 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;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndexInA = i;
}
} else {
dp[i][j] = 0; // reset — the run breaks here, it does NOT carry forward like LCS does
}
}
}
return { length: maxLen, substring: a.slice(endIndexInA - maxLen, endIndexInA) };
}Reading dp[m][n], the way every other two-sequence table on this site does, is a
real, confidently wrong answer here — not a rare edge case. On this page's own example,
dp[7][6] is 0 (the two strings' last characters, B and
A, don't match), while the true answer is 2. A 20,000-trial sweep over random 8-character
strings from a 4-letter alphabet found the corner disagreeing with the real global maximum on
93.7% of trials — reading the corner is wrong far more often than it's right, the
reverse of every other entry on this page's guide. The fix isn't a smarter formula, it's tracking a
running maximum over the whole table as it fills, the way this page's own demo does.
Reusing Longest Common Subsequence's mismatch rule — carry forward the better neighbor instead of resetting to 0 — doesn't produce a slightly-too-long substring, it silently computes a different problem's answer instead. Try it live above by switching to bug: carry forward like LCS: on this page's own example the reported length climbs to 4, exactly the two strings' longest common subsequence length, not a real contiguous run at all — the "substring" a naive read-off would report doesn't actually appear unbroken in either string. The same 20,000-trial sweep found this variant disagreeing with the true answer on 93.4% of trials, always by overcounting (a carried-forward value can only be greater than or equal to what a true reset would leave, never less), which makes the bug easy to miss on a hand-picked example where the two problems' answers happen to coincide.
More than one longest common substring can exist, and unlike Longest Common Subsequence's
ties, they don't have to be the same text. This page's own table has three cells tied
at the maximum value of 2: two of them both hold "AB" (at different positions in each
string), but the third holds "BD" — a completely different pair of characters, equally
valid, equally long. An implementation that keeps the first max it sees while scanning top-to-bottom,
left-to-right reports "AB"; one that keeps the last one reports "AB" too here,
but only because the tie happens to resolve that way on this specific input — swap the scan order (or
just pick a different tied cell to keep) and a different, differently-worded string comes back with
exactly the same claimed length. "The longest common substring" is really "a longest common substring";
treat the exact text as one valid answer among possibly several, not the unique one implied by the
definite article.
Time: O(m·n) — the same one-decision-per-cell cost as Longest Common
Subsequence. Space: O(m·n) for the full table as shown above, but this
entry can drop to O(min(m,n)) — keeping only a prev row and a curr
row — without losing the actual substring, unlike Longest Common Subsequence's own space
trade-off. Longest Common Subsequence's two-row version can only report a length, because recovering the
characters needs backtracking through cells that no longer exist once overwritten. This entry never
backtracks in the first place: the moment a new global maximum is set, its ending row index and length
are already enough to slice the substring straight out of a, so trimming the table to two
rows costs nothing but the memory itself.
Longest common substring shows up anywhere two pieces of text need their longest shared run compared, not just their shared content in any order — a rough plagiarism check, or finding the longest overlap to stitch two DNA reads together at. Longest Common Subsequence is the entry to reach for instead when the match is allowed to skip around; Edit Distance when the question is the cost to transform one string into the other rather than how much they already share.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other eleven Dynamic Programming entries side by side.