Longest Common Subsequence
Time: O(mn)Space: O(mn)Find the longest subsequence present in both strings. A subsequence need not be contiguous. Classic DP with optimal substructure: LCS(s1,s2) = LCS(s1[:-1],s2[:-1])+1 if last chars match, else max(LCS(s1[:-1],s2), LCS(s1,s2[:-1])).
SlowFast
1 / 52DP Table
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
Inputs
Phase
Fill Table
Description
Initialize DP table with zeros. dp[i][j] = length of LCS of s1[0..i-1] and s2[0..j-1].
Legend
Default
Active cell
Backtrack path
Header