Pattern visualizer
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]. Animated on: s1="ace", s2="abcde", find LCS length.
Dynamic Programming
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