⚡ AlgoZen_
~/home/dynamic_programming/longest_common_subsequence6 / 6

Longest Common Subsequence

Advanced

Find the length of the longest subsequence common to two sequences. Uses a 2D DP table: if characters match, extend the previous LCS; otherwise take the best of skipping one character from either string.

time:O(m × n)
space:O(m × n)
⚡ +300_XP
step[1/38]
> Start
""
0
A
0
C
0
B
0
D
0
E
0
LCS of "ABCDE" and "ACBDE". Each row computes LCS lengths for one character of s1 vs all of s2.

// tap NEXT STEP to walk through one step at a time