Longest Common Subsequence
The key insight: when the current characters from both strings match, they must belong together in the longest common subsequence, so you can lock them in and grow diagonally from the answer to the two shorter prefixes; when they don't match, the best you can do is inherit whichever neighbor — dropping a character from s1 or from s2 — already found the longer match. dp[i][j] holds the LCS length between the first i characters of s1 and the first j characters of s2, built up one cell at a time from those smaller prefixes. The final answer sits in the bottom-right cell, dp[m][n].
Dynamic Programming
step 1 / 7
Row i=0: empty s1 prefix, LCS length is 0 for all s2 prefixes
1FUNCTION lcs(s1, s2):2 m = length of s1, n = length of s23 dp = an (m+1) by (n+1) grid filled with 04 FOR i from 1 to m:5 FOR j from 1 to n:6 IF s1[i-1] equals s2[j-1]:7 dp[i][j] = dp[i-1][j-1] + 1 (extend the diagonal match)8 ELSE:9 dp[i][j] = the larger of dp[i-1][j] and dp[i][j-1]10 RETURN dp[m][n]
← / → step · space play · Home restart
Every step in words
Show all 7 steps
- Row i=0: empty s1 prefix, LCS length is 0 for all s2 prefixes
- Row i=1 (s1="a"): dp[1][j] = 1 for all j, 'a' matches s2[0] and propagates
- Row i=2 (s1="ac"): dp[2][3]=2 because s1[1]='c'==s2[2]='c', dp[2][3]=dp[1][2]+1=1+1=2
- Row i=3 (s1="ace"): dp[3][5]=3 because s1[2]='e'==s2[4]='e', dp[3][5]=dp[2][4]+1=2+1=3, final answer
- Key cell: s1[2]='e' == s2[4]='e', so dp[3][5] = dp[2][4] + 1 = 2 + 1 = 3
- Earlier key cell: s1[1]='c' == s2[2]='c', dp[2][3] = dp[1][2] + 1 = 1 + 1 = 2
- Answer: dp[3][5] = 3, LCS is "ace" — characters appear in order in both strings
Now solve it yourself
Watching is the first half. The second is writing it without the animation.