Longest Common Subsequence
Medium2-D dynamic programming
Given two strings text1 and text2, return the length of the longest string that is a subsequence of both, or 0 if they share no letter.
A subsequence keeps some of a string’s characters in their original order, not necessarily next to each other: "ace" is a subsequence of "abcde".
Examples
Input: text1 = "kitten", text2 = "sitting" Output: 4
ittn is in both, in order.
Input: text1 = "pqr", text2 = "xyz" Output: 0
The two strings share no letter.
Constraints
1 ≤ text1.length, text2.length ≤ 1000- Both strings hold lowercase English letters only.
Stuck?
Hint 1
Compare the last characters. If they match, they end the common subsequence; if not, drop the last character of one string or the other and keep the better result.
Hint 2
Fill a table where dp[i][j] is the answer for the first i letters of text1 and the first j of text2: a match is dp[i - 1][j - 1] + 1, otherwise max(dp[i - 1][j], dp[i][j - 1]).
The idea
Compare the last letters of two prefixes. If they match, they can end the common subsequence together; if not, at least one of them is not in it, so drop one or the other and keep the better answer. Each answer needs only answers for shorter prefixes, so a table filled row by row has them ready.
Time O(m · n)Extra space O(n), two rows as long as text2
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
The row for zero letters of text1, which shares nothing with any prefix of text2. Entry j stands for the first j letters of text2, so entry 0 is the empty prefix.
function longestCommonSubsequence(text1, text2) { let previous = new Array(text2.length + 1).fill(0); for (let i = 1; i <= text1.length; i++) { const current = new Array(text2.length + 1).fill(0); for (let j = 1; j <= text2.length; j++) { if (text1[i - 1] === text2[j - 1]) { current[j] = previous[j - 1] + 1; } else { current[j] = Math.max(previous[j], current[j - 1]); } } previous = current; } return previous[text2.length];}The trap
Matching each letter of text1 with the first copy it can find in text2, and never taking it back, gives the right length when the strings line up neatly. But a letter matched far ahead in text2 can use up the letters that later ones needed, and skipping that letter would have left room for more matches. Only a table that weighs both choices at every pair gets those strings right.
function longestCommonSubsequence(text1, text2) { let count = 0; let from = 0; for (const letter of text1) { const at = text2.indexOf(letter, from); // grabs the first match it sees if (at !== -1) { count++; from = at + 1; } } return count;}