Longest Common Subsequence
MediumCompare the last characters of two prefixes. A match extends the diagonal, a mismatch takes the better of dropping one character from either side.
two sequencesprefix state
TimeO(n * m)
SpaceO(min(n, m))
Inputfirst string | second string
-
B
D
C
A
B
A
-
0
0
0
0
0
0
0
A
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0
C
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0
D
0
0
0
0
0
0
0
A
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0
cell being filledcells it readsreconstructed answer
Row and column zero mean one string is empty, so the common subsequence is empty.
1 / 44
for i in 1..n:
for j in 1..m:
if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Why it matters
Edit distance, shortest common supersequence and diff tools are the same recurrence with different costs.
Keyboard
space play← → stepr restartctrl K search
More in Dynamic Programming
Next visualiser
Coin Change