Longest common subsequence
Compare the words one letter pair at a time. If the last letters match, the answer is one more than the answer without both of them. If not, drop one letter or the other and keep whichever answer is better. A table holds every one of those smaller answers, so each is worked out once.
empty table
Find the longest run of letters that appears, in order, in both "abcde" and "ace". The letters do not have to be next to each other.
1function lcs(a, b) {2 const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));3 for (let i = 1; i <= a.length; i++) {4 for (let j = 1; j <= b.length; j++) {5 if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;6 else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);7 }8 }9 return dp[a.length][b.length];10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n · m | every cell of the table is filled |
| average | n · m | any two words |
| worst | n · m | plain recursion without the table is exponential |
| space | n · m | the table; two rows are enough for the length alone |
Where it breaks
- Subsequence, not substring. The shared letters keep their order but can have gaps. Pick abcde · ace: "ace" is the answer even though it never appears as one block in "abcde".
- The answer is not unique. Pick abcbdab · bdcaba: the length is 4, but "bcba", "bdab" and "bcab" all qualify. Walking back the table picks one of them, depending on how ties are broken.
- Where it is used. The diff tool that shows changed lines between two files is built on exactly this table, with whole lines in place of letters.