Problem 55 · Dynamic Programming

Longest Common Subsequence

MediumClassic DSA & systems

01Problem

Given two strings, return the length of their longest common subsequence.

02Key insight

dp[i][j] = dp[i-1][j-1] + 1 on match, else max(dp[i-1][j], dp[i][j-1]). This is the core of diff tools; roll to one row for O(min(m,n)) space.

03Solution

solution.pypython10 lines

def longest_common_subsequence(a: str, b: str) -> int:
    if len(a) < len(b):
        a, b = b, a
    prev = [0] * (len(b) + 1)
    for ca in a:
        cur = [0] * (len(b) + 1)
        for j, cb in enumerate(b, 1):
            cur[j] = prev[j - 1] + 1 if ca == cb else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]

Try it first.

TimeO(m*n)

SpaceO(min(m,n))

tests.py · 4 passing

tests.pypython4 lines

assert longest_common_subsequence("abcde", "ace") == 3
assert longest_common_subsequence("abc", "def") == 0
assert longest_common_subsequence("", "abc") == 0
assert longest_common_subsequence("bsbininm", "jmjkbkjkv") == 1

04Staff-level follow-up

Diffing two huge files? Myers' O((m+n)*D) algorithm is fast when the edit distance D is small, and Hirschberg recovers the alignment in linear space.