Editor

Longest Common Subsequence

#135 · Dynamic programming · Advanced · 125 XP · about 22 min

A subsequence of a string keeps some of its characters in their original order, though not necessarily side by side: "pto" is a subsequence of "python". Write lcs_length(a, b) that returns the length of the longest string that is a subsequence of both a and b.

Examples

lcs_length("python", "typhoon")  # returns 4
lcs_length("kitten", "sitting")  # returns 4
lcs_length("abc", "xyz")         # returns 0

"python" and "typhoon" share "thon" (and also "phon"), so the answer is 4.

Constraints

  • 0 <= len(a), len(b) <= 1000

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.