Skip to content
GKgkml.dev
← Problem set
#1143MediumDynamic programming

Longest Common Subsequence

The tell: Two sequences compared for shared order — the archetypal 2-D DP.

How you get there

  1. 1dp[i][j] is the LCS of the first i and first j characters.
  2. 2Matching characters extend the diagonal result by one.
  3. 3Otherwise take the better of dropping one character from either string.

Solution

Python
def longest_common_subsequence(a: str, b: str) -> int:
    if len(b) > len(a):
        a, b = b, a
    prev = [0] * (len(b) + 1)

    for ch_a in a:
        cur = [0] * (len(b) + 1)
        for j, ch_b in enumerate(b, start=1):
            cur[j] = prev[j - 1] + 1 if ch_a == ch_b else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]
Time
O(n · m)
Space
O(min(n, m))

What goes wrong

Confusing subsequence with substring — a subsequence need not be contiguous.

Test yourself on DSANext: Unique Paths →