The longest thread through both strings
Two positions agree — extend a match; they don't — take the better of skipping one letter from either. About 13 minutes.
Compare the last letters
Take two words, like "abcde" and "ace". What's the longest run of letters they share, in the same order, with gaps allowed?
Look at the last letter of each. If they match, that letter is part of the answer: count 1 and compare everything before them. If they don't match, one of the two last letters isn't in the answer. So try dropping it from the first word, then from the second, and keep the better result.
A grid of prefixes
Every question in that rule is about the start of each word: the first few letters of one against the first few of the other. So build a grid with one word across the top and the other down the side. Each box answers "how much do these two starts have in common?"
The top row and left column compare against nothing, so they're 0. Every other box looks at the box diagonally up-left (on a match) or at the box above and the box to the left (on a mismatch). The bottom-right box is the answer.
if a[i - 1] == b[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1Row 0 and column 0 are empty prefixes: they share nothing, so 0.
Comparing "ab" with "ab": the starts "a" and "a" share 1 letter. Both words end in b, which matches. How much do the whole words share?
- A2
- B1
- C3
Show the answer
2. The matching b adds 1 to what "a" and "a" shared: 1 + 1 = 2.
Longest common subsequence
You get two strings a and b. Return the length of their longest common subsequence: the longest list of letters that appears in both strings in the same order, but not necessarily next to each other.
a = "abcde", b = "ace" → 3
0 ≤ a.length, b.length ≤ 1,000 · lowercase English letters