Longest Common Subsequence

Watch 2D DP fill a table cell by cell to find the longest subsequence common to both strings, then backtrack to reconstruct it.

Time: O(m × n)

Space: O(m × n)

2D DP Table

Backtracking

String 1

String 2

Speed: 800ms

Fast (300ms)Slow (2000ms)

Step 1 of 0Phase: start

String 1:

String 2:

Current cell

Match

Backtrack path

Click Play to begin

Time:O(m × n)

Space:O(m × n)

Space-optimized:O(min(m,n))

Type:2D DP

Question 1 of 3

When two characters match in the LCS DP table, what is dp[i][j]?

DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)