Longest common subsequence
Find the longest list of items that appears, in the same order, inside both of two sequences.
O(m × n)Space O(m × n)11 practice problemsStep-through pictureThe idea
Given two sequences, such as two strings or two lists of lines, the longest common subsequence, or LCS, is the longest sequence you can get from both by deleting items without reordering. For "abcde" and "ace", the LCS is "ace", length 3. The kept items don't need to be next to each other.
The DP table compares every prefix of the first sequence with every prefix of the second. A prefix is the start of a sequence: the first i items. Cell len[i][j] holds the LCS length of the first i items of a and the first j items of b.
This is how text diff tools decide which lines stayed the same between two versions of a file. Lines in the LCS are unchanged; every other line was deleted or added.
An everyday example
Matching two people's to-do lists
Two people wrote to-do lists for the same day, and you want the longest list of tasks they both planned in the same order. You compare the lists from the top. When both lists have the same task at the current spot, it is in common, so you count it and move past it in both lists. When they differ, you try skipping a task in one list or the other and keep the better result.
| In the example | In the code |
|---|---|
| The two lists | Sequences a and b |
Best match using the first i and j tasks | len[i][j] |
| Both lists have the same task here | a[i - 1] === b[j - 1] |
| Count it and move past it in both | len[i - 1][j - 1] + 1 |
| Skip a task in one list or the other | Math.max(len[i - 1][j], len[i][j - 1]) |
From the slow way to longest common subsequence
- Start with brute force: list every subsequence of
a, check whether each one also appears in order insideb, and keep the longest.ahas2^msubsequences formitems, and each check walks throughb. Two strings of 30 characters already mean over a billion subsequences. - Think about the last items instead. Compare the last item of
awith the last item ofb. If they are equal, they can be paired as the last item of the common subsequence, and the rest is the same question on both strings with the last item removed. If they differ, at least one of them is not used, so the answer is the better of two smaller questions: drop the last item ofa, or drop the last item ofb. - Every smaller question is about a prefix of
aand a prefix ofb: the firstiitems of one and the firstjof the other. The recursion keeps reaching the same pairs (i,j) along different paths, but there are only(m + 1) × (n + 1)of them. So store one number per pair in a tablelen. - Row 0 and column 0 stand for an empty prefix, and they stay 0. Every other cell reads the cell above, the cell to the left, or the cell diagonally up and to the left, so filling row by row, left to right, always reads finished cells. The bottom-right cell is the answer. That double loop is the longest common subsequence.
How it works
- Make a table
lenwitha.length + 1rows andb.length + 1columns, all0. Row 0 and column 0 stand for an empty prefix, which has nothing in common with anything. - Fill the table row by row, with
igoing overaandjgoing overb. - If
a[i - 1]equalsb[j - 1], the last items match, solen[i][j] = len[i - 1][j - 1] + 1. - Otherwise one of the two last items is not in the LCS, so
len[i][j] = Math.max(len[i - 1][j], len[i][j - 1]). - The answer is
len[a.length][b.length], the bottom-right cell. - To list the common items, start at the bottom-right and walk back: on a match go diagonally up-left and record the item; otherwise move toward the larger neighbor.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function lcsLength(a, b) {const rows = a.length;const cols = b.length;const len = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));for (let i = 1; i <= rows; i++) {for (let j = 1; j <= cols; j++) {if (a[i - 1] === b[j - 1]) {len[i][j] = len[i - 1][j - 1] + 1;} else {len[i][j] = Math.max(len[i - 1][j], len[i][j - 1]);}}}return len[rows][cols];}
How fast it is
| Time | O(m × n) |
|---|---|
| Extra memory | O(m × n) |
One cell for every pair of prefixes, each filled with a comparison. Keeping only the previous row is enough for the length, which uses O(n) space.
- Best case
O(m × n)Any input, even two identical strings: every one of the
m × ncells is still filled. - Average case
O(m × n)Any input: one comparison and one copy or
Math.maxper cell. - Worst case
O(m × n)The same. Two 1,000-line files take a million cells whether they share every line or none.
Common mistakes
- Forgetting the extra row and column and reading
len[-1][j]. Size the tablerows + 1bycols + 1. - Comparing
a[i]withb[j]in a table that starts at 1. Rowiholds the itema[i - 1]. - Mixing up subsequence and substring. A common substring must be contiguous; its table resets to
0on a mismatch instead of taking a max. - On a match, adding one to
Math.max(...)of the neighbors instead of the diagonal cell. That can count the same item twice.
When to use it
Look for these clues in a problem:
- There are two strings or two lists, and the question is about what they have in common in order.
- The question asks how many deletions or insertions turn one sequence into the other.
- You need a diff: which items were kept, removed, or added between two versions.
- The items can be skipped but not reordered.
Check yourself
Answer each one in your head first, then open it.
Why does the table have an extra row and column?
They stand for empty prefixes, whose LCS is 0. They let the first real row and column read a neighbor without special cases.
On a match, why read the diagonal instead of Math.max of the neighbors plus 1?
The cell above may already have used b[j - 1], and the cell to the left may already have used a[i - 1]. Adding 1 to them could pair one item twice. The diagonal excludes both.
In the trace, why is len[2][2] only 1 when both m and a appear in both words?
They appear in opposite orders: m then a in "maple", a then m in "ample". A common subsequence keeps the order, so only one of them can be used.
What is the fewest number of deletions that makes a and b equal?
m + n - 2 × LCS: delete every item that isn't in the LCS from both. For "maple" and "ample", that is 5 + 5 - 8 = 2.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 11 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingmedium
Go further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The table keeps one promise: when the loops reach cell (i, j), the cells above it, to its left, and diagonally up-left already hold the LCS length for their prefixes. Row 0 and column 0 are right from the start, because an empty prefix shares nothing.
When the last items match, pairing them is always safe. Take any longest common subsequence of the two prefixes. If it doesn't use both last items, you can change its last item to use them, or add them, without making it shorter. So some longest one ends with this pair, and its length is len[i - 1][j - 1] + 1.
When the last items differ, they can't both be the final pair, so at least one of them is unused. If a[i - 1] is unused, the answer is len[i - 1][j]; if b[j - 1] is unused, it is len[i][j - 1]. Taking the larger covers both cases. Each cell is filled once in an order that only reads finished cells, so the bottom-right cell ends up holding the LCS of the whole of a and b.
Going deeper
3 more ideas
What each cell of the table means
len[i][j] is the length of the longest common subsequence of a.slice(0, i) and b.slice(0, j). Row i adds the item a[i - 1]; column j adds the item b[j - 1]. The extra row and column of zeros mean "one of the prefixes is empty".
Why the transition is right
Look at the last items of the two prefixes. If they are equal, it never hurts to pair them, so the answer is one more than the answer without both. If they differ, they can't both be the last item of a common subsequence, so drop one of them; you don't know which, so try both and keep the larger.
How much work it does
There are (m + 1) * (n + 1) cells, each filled in constant time, so the time and space are O(m * n). Two files of 1,000 lines each need a million cells, which is fine. For the length alone, two rows are enough, which brings the space down to O(n).
Work it by hand
Every step in a table, with why
Find the LCS length of two 5-letter words. Each row of the trace fills one whole row of len.
a = "maple", b = "ample"
| Step | i | a[i - 1] | Matches at j | len[i], j = 0 to 5 | What happens | Why |
|---|---|---|---|---|---|---|
| 1 | 0 | - | - | 0, 0, 0, 0, 0, 0 | Empty prefix of a | Row 0 means no letters of a, so nothing can be in common. Line 4 already filled it with zeros. |
| 2 | 1 | m | 2 | 0, 0, 1, 1, 1, 1 | m pairs with b[1] | At j = 2, a[0] equals b[1], so the cell is the diagonal 0 plus 1. Cells to the right copy that 1 from the left. |
| 3 | 2 | a | 1 | 0, 1, 1, 1, 1, 1 | a pairs with b[0] | At j = 1, the letter a matches. At j = 2, "ma" against "am" is a tie between above and left, both 1: only one letter can be shared. |
| 4 | 3 | p | 3 | 0, 1, 1, 2, 2, 2 | Diagonal 1 plus 1 | At j = 3, p matches, and the diagonal cell len[2][2] is 1, so the cell becomes 2. |
| 5 | 4 | l | 4 | 0, 1, 1, 2, 3, 3 | Diagonal 2 plus 1 | l matches at j = 4 and extends the 2 from the diagonal to 3. |
| 6 | 5 | e | 5 | 0, 1, 1, 2, 3, 4 | Diagonal 3 plus 1; done | e matches at the last column. The loops end and line 14 returns len[5][5]. |
It returns 4. Walking back from the corner gives "aple" or "mple", depending on how ties are broken at cell (2, 2): both are correct, since only one of m and a can be kept.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Longest common subsequence | O(m × n) | O(m × n) | You need the items themselves, or the inputs are up to a few thousand items each. |
| LCS with two rows | O(m × n) | O(n) | You only need the length, and the inputs are long. |
| Myers' diff | O(n · d) | O(n) | The two sequences are long and nearly the same, where d is the number of differences, as in version control. |
| Try every subsequence | O(2^n) | O(n) | Only to check the table on strings of about 15 items. |
Extra memory: O(m × n) for the full table. For the length alone, keep two rows (or one row plus the saved diagonal value) for O(n) space, but then you can't walk back to list the items.
How the steps grow
- Longest common subsequence, LCS with two rows, Myers' diff
O(m × n) - Try every subsequence
O(2^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Longest common subsequence | 100 | 1 million | 1 trillion |
| LCS with two rows | 100 | 1 million | 1 trillion |
| Myers' diff | 100 | 1 million | 1 trillion |
| Try every subsequence | 1,024 | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
- One string is empty:
a = "" rowsis 0, the loops never run, and it returnslen[0][cols], which is 0.- Identical strings
- Every diagonal cell is a match, so the answer is the full length.
- No shared items:
"abc"and"xyz" - No cell ever matches, every cell is a max of zeros, and it returns 0.
- Repeated letters:
"aaa"and"aa" - It returns 2. Each match uses the diagonal, so one letter of
bcan't be paired twice. - Arrays of lines instead of strings
- The same code works on arrays, since it only indexes and compares with
===. Lines that are strings compare by content. Objects compare by reference, so compare an id or a key instead.
Variations and follow-ups
Twists interviewers add
Listing the common items
Start at the bottom-right cell. If a[i - 1] === b[j - 1], record that item and move diagonally. Otherwise move to the larger of the cell above and the cell to the left. Reverse the recorded items at the end. This needs the full table.
Longest common substring
If the shared part must be contiguous, a match still adds 1 to the diagonal, but a mismatch resets the cell to 0. The answer is the largest cell anywhere, not the corner.
Shortest common supersequence
The shortest sequence that contains both a and b as subsequences has length m + n - LCS. Every item of the LCS is shared, and every other item must appear once.
Line diffs
Diff tools run this on lines. Lines in the LCS are unchanged, lines of a outside it were deleted, and lines of b outside it were added. Real diff tools often use Myers' algorithm, which is much faster when the two files are mostly the same.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from two sequences and "in the same order, not necessarily next to each other", or from diff, alignment, and "fewest deletions to make them equal" questions.
- Explain the cell as two prefixes: "
len[i][j]is the LCS of the firstiitems ofaand the firstjofb". Then give the match rule and the mismatch rule, each in one sentence. - Fill a tiny table by hand, such as
"ab"and"ba", which should give 1. It checks the extra row and column, and the off-by-one between rowiand itema[i - 1]. - Expect "how do you print the subsequence?" (walk back from the corner) and "can you use less memory?" (two rows for the length, at the cost of not being able to walk back).
Where frontend code uses it
The same idea in real UI code
- Code review tools show line diffs between two versions of a file. The lines kept are a longest common subsequence; fast diff algorithms like Myers' find the same kind of answer with less work.
- Collaborative editors and "show changes" views compare two drafts word by word or character by character with this table.
- Snapshot test runners print a diff of the expected and actual output so you can see which lines changed.