Longest common subsequence
mediumThe table gives the length; the traceback gives the subsequence. This is the algorithm behind `diff`, DNA alignment and plagiarism detection.
O(m × n)Space O(m × n)Saved in this browser - no sign-up, nothing sent anywhere.
How longest common subsequence works
dp[i][j] is the length of the longest common subsequence of the first i characters of a and the first j of b. When a[i-1] equals b[j-1], the two characters can end the subsequence together, so the answer extends the diagonal: dp[i-1][j-1] + 1. When they differ, at least one must be dropped, and the cell takes whichever loss is cheaper: max(dp[i-1][j], dp[i][j-1]).
Brute force enumerates subsequences of one string and checks each against the other - 2^m candidates, which is 128 for a 7-character string and over a million by 20 characters. Every one of those checks reduces to the same question about shorter prefixes. There are only (m + 1) × (n + 1) distinct prefix pairs - 56 cells for the default 7 by 6 input - and each is filled once.
The length in dp[m][n] is half the story. The subsequence itself is recovered by walking backwards from the corner: step diagonally on a match, collecting the character, otherwise move toward the larger neighbour. That traceback is what diff tools actually ship - matched characters are the unchanged lines, and everything else renders as an insertion or deletion.
Step by step
- Take a = abc and b = bac. The table is 4 by 4, and row 0 and column 0 hold zeros - an empty prefix shares nothing.
- Row 1 compares a against b, a, c: a mismatch gives 0, then a matches a - diagonal 0 plus 1 - and the 1 carries right.
- Row 2: b matches b in column 1, taking the diagonal zero plus 1. The rest of the row holds at 1 - two competing length-1 answers.
- Row 3: c finally matches c in the corner. The diagonal holds dp[2][2] = 1, so dp[3][3] = 2.
- Traceback: the corner's c matched - collect it and step diagonally to dp[2][2]. There b and a mismatch, so move up to the tied neighbour dp[1][2].
- At dp[1][2] the two a characters match - collect a and step out of the table. Reversing what was collected gives ac, length 2, exactly as the corner promised.
Complexity
| Worst case time | O(m × n) |
|---|---|
| Space | O(m × n) |
Replaces checking all 2^m subsequences with (m+1)(n+1) cells.
Reference implementation
Python
def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
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
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out, i, j = [], m, n # traceback
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1]); i -= 1; j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(out))JavaScript
function lcs(a, b) {
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++)
dp[i][j] = a[i - 1] === b[j - 1]
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
let out = "", i = m, j = n;
while (i && j) {
if (a[i - 1] === b[j - 1]) { out = a[i - 1] + out; i--; j--; }
else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
else j--;
}
return out;
}Worth noticing
Match means diagonal, mismatch means the better of two
When the characters agree, the answer is one longer than the problem with both dropped - a diagonal step. When they disagree, one of them has to go, and the table takes whichever loss is cheaper.
Subsequence, not substring
Characters keep their order but need not be adjacent. That is why the diagonal step is allowed to skip - and why 'abcbdab' and 'bdcaba' share 'bcba' despite looking unrelated.
The traceback is where the actual answer lives
dp[m][n] gives only the length. Walking backwards - diagonally on a match, otherwise towards the larger neighbour - reconstructs the subsequence itself. Most DP problems need this second phase.
This is what `diff` runs on
Version control diffs, DNA alignment and plagiarism detection are all LCS with a scoring tweak. Edit distance is the same table with different arithmetic.
Common pitfalls
- Confusing subsequence with substring. LCS characters keep their order but need not be adjacent - abcbdab and bdcaba share bcba, which is contiguous in neither.
- Indexing the strings with i instead of i - 1. The table is offset by the empty-prefix row, so cell (i, j) compares a[i-1] with b[j-1].
- Writing the recursion without memoisation. It is correct and exponential - the same prefix pair gets recomputed an enormous number of times.
- Space-optimising to two rows and then needing the subsequence. The rolling version keeps the length but destroys the table the traceback walks.
- Expecting one specific answer. Several subsequences can tie at the maximum length; this implementation breaks traceback ties by moving up.
Where it is used
- Diff tools and version control - unchanged lines are the LCS, everything else renders as additions and deletions.
- DNA and protein sequence comparison, where shared subsequences indicate common structure.
- Plagiarism and near-duplicate detection across documents and code submissions.
- LeetCode 1143 and the family of two-string DP interview questions that reuse this exact table shape.
Frequently asked questions
What is the time and space complexity of LCS?
Both are O(m × n) for strings of length m and n - the table has (m + 1) × (n + 1) cells and each fills in constant time. That replaces checking all 2^m subsequences of the first string. Keeping only two rows shrinks memory when just the length is needed.
What is the difference between longest common subsequence and longest common substring?
A substring must be contiguous; a subsequence only keeps relative order. abcbdab and bdcaba have LCS bcba, length 4, but their longest common substring is shorter. The substring variant uses a similar table where a mismatch resets the cell to 0 instead of taking a maximum.
How do I recover the actual subsequence, not just its length?
Walk backwards from dp[m][n]. On a match, collect the character and step diagonally; otherwise step to the larger of the cell above and the cell to the left. Reverse the collected characters at the end. The visualizer animates this exact walk after the table completes.
How is edit distance related to LCS?
Same table shape, different arithmetic: both compare every prefix pair of two strings, but LCS maximises kept characters while edit distance minimises changes. With only insertions and deletions allowed, they measure one quantity two ways - the distance equals m + n - 2 × LCS.