Given two strings, return the length of their longest common subsequence. A subsequence keeps the order of characters, but may skip some.
DSA Animator › DSA Revision › Dynamic Programming › Longest Common Subsequence
Remember: match means diagonal plus 1, mismatch means the larger of up and left. Prefix tables solve most two string problems. The video solves Longest Common Subsequence (LeetCode 1143, Medium) with the 2D String DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Longest Common Subsequence animation.
Given two strings, return the length of their longest common subsequence. A subsequence keeps the order of characters, but may skip some.
For abcde and ace, the answer is 3, because ace appears in both, in order.
Comparing every subsequence of one string with every subsequence of the other is exponential. Instead, compare prefixes.
Let dp of i and j be the answer for the first i characters of the first string and the first j of the second. An empty prefix gives 0, so the first row and column are 0. If the two last characters match, take dp of i minus 1, j minus 1, plus 1. Otherwise, drop one character from either string, and take the larger of the two results. The bottom right cell is the answer.
The a of abcde matches the a of ace, so that cell becomes 1, and the row stays 1. b matches nothing, so its row copies the values from above. c matches the c of ace, so it becomes 1 plus 1, which is 2. d matches nothing, so it copies 2. e matches the e of ace, so it becomes 2 plus 1, which is 3. The answer is 3.
In code, create a table with one extra row and column of zeros. For each pair i and j, compare the characters at i minus 1 and j minus 1. On a match, take the diagonal plus 1, otherwise the larger of the cell above and the cell on the left. Return the bottom right cell, so it's O of m times n.
Remember: match means diagonal plus 1, mismatch means the larger of up and left. Prefix tables solve most two string problems.