CODING CHALLENGE · N°37

Longest Common Subsequence

Medium Dynamic ProgrammingStrings

The DP at the heart of "git diff", DNA alignment and spell-correction: the length of the longest subsequence common to two strings (characters in order, gaps allowed). A classic 2-D table fills in O(m·n). Solve it in Python or TypeScript, with hidden tests.

The problem

Given two strings a and b, return the length of their longest common subsequence — the longest sequence of characters appearing in both, left-to-right, not necessarily contiguous. This is the core of diff tools (the LCS of two files is the set of unchanged lines).

EXAMPLE 1

Input a = 'abcde', b = 'ace'

Output 3

"ace" appears in both, in order

EXAMPLE 2

Input a = 'aggtab', b = 'gxtxayb'

Output 4

"gtab" is common to both

EXAMPLE 3

Input a = 'abc', b = 'def'

Output 0

nothing in common

CONSTRAINTS

0 ≤ a.length, b.length; either may be empty (then the answer is 0).
Subsequence ≠ substring: characters keep their order but may have gaps.
Aim for O(m·n) time with a 2-D DP table (or a rolling 1-D row).

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement lcs(a, b): fill a table where dp[i][j] is the LCS length of the first i chars of a and first j of b. On a matching char, extend the diagonal; otherwise take the best of dropping one char from either string.

HINTS — 4 IDEAS

Define dp[i][j] = LCS of a[:i] and b[:j]. The empty row and column are all 0.
If a[i-1] == b[j-1], the characters can join the subsequence: dp[i][j] = dp[i-1][j-1] + 1.
Otherwise, skip one character: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
The answer is dp[m][n]. You can compress the table to two rows if you like.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Dynamic programming over the two sequences: dp[i][j] is the LCS length of the first i and first j elements. If the current elements match, dp[i][j] = dp[i−1][j−1] + 1; otherwise it is the max of dropping one element from either side. Backtrack through the filled table to reconstruct the actual common subsequence — which is the basis of a diff.

Complexity

Time O(n·m); space O(n·m) to reconstruct, or O(min(n,m)) with rolling rows if you only need the length.

Common mistakes

Confusing subsequence (not contiguous) with substring (contiguous) — different problems.
Getting the mismatch recurrence wrong (it is the max of the two “drop one” options).
Computing the length but forgetting to backtrack to recover the sequence itself.

Where this shows up

LCS is the core of diff tools — git diff and file comparison find the longest common subsequence, and everything not in it is an insertion or deletion. The same DP underlies version control, DNA sequence alignment, and the whole edit-distance family.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA