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

Explore the topic

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

Algorithms & DSA