Longest Common Subsequence

Medium#1143two strings

You get two words. A subsequence is what is left of a word after crossing out some of its letters, the order kept. Find the length of the longest subsequence the two words share. Our example: "plum" and "lump" share "lum", so the answer is 3.

1143 Longest Common SubsequenceWalkthrough · 1×

Example: a = "plum", b = "lump". Both have a p, but at opposite ends: watch the last cell drop it.

lumpplum
filledthis step, letters comparedread fromanswer and its letters

dp[i][j]: the longest common subsequence of the first i letters of plum and the first j letters of lump

01/39
restart · back · play · step
Speed
1function lcs(a, b):
2 dp = table of len(a) + 1 by len(b) + 1
3 set row 0 and column 0 to 0 // an empty prefix
4 for i from 1 to len(a):
5 for j from 1 to len(b):
6 if a[i - 1] == b[j - 1]:
7 dp[i][j] = dp[i - 1][j - 1] + 1
8 else:
9 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
10 return dp[len(a)][len(b)]
state
dp
[[–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –]]
i
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. If the last letters of two prefixes are equal, some longest common subsequence ends with that letter: whatever the answer used instead can be swapped for it. So the cell is the diagonal plus one.
  2. If they differ, at least one of the two letters is not at the end of the answer, so the answer is in the cell above or the one to the left: the larger of the two.
  3. Every cell reads only cells with shorter prefixes, which row-by-row order has already filled. A shared letter in the wrong place, like p here, never adds to the count.

Complexity

Time O(n × m) for words of lengths n and m: one cell per pair of prefixes, each filled from three neighbours. Memory O(n × m) for the table; keeping only the row above brings it down to O(m).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.