Builds on Grid DP, which you haven’t finished yet.
Two-Sequence DP (Longest Common Subsequence, Edit Distance)
You're handed two strings, text1 and text2. A subsequence of a string is whatever remains after deleting zero or more of its characters while keeping the survivors in their original order -- for instance, "ace" can be pulled out of "abcde" this way. A common subsequence is a subsequence the two strings share.
Report the length of the longest subsequence they have in common, or 0 if they share none.
Two-Sequence DP
dp[i][j] = the answer for text1[:i] and text2[:j] ➔ built from the cell above, the cell to the left and the diagonal ➔ 1D rolling row| 1 | def longest_common_subsequence(text1: str, text2: str) -> int: |
| 2 | """Longest Common Subsequence with two rolling rows. |
| 3 | Time: O(M * N) | Space: O(min(M, N)) |
| 4 | """ |
| 5 | if len(text1) < len(text2): |
| 6 | text1, text2 = text2, text1 # text2 is the shorter string |
| 7 | |
| 8 | m, n = len(text1), len(text2) |
| 9 | # prev, curr: two rolling rows of the DP table; index 0 of each row is the empty prefix |
| 10 | prev = [0] * (n + 1) |
| 11 | |
| 12 | for i in range(1, m + 1): |
| 13 | curr = [0] * (n + 1) |
| 14 | for j in range(1, n + 1): |
| 15 | # 1. Extend Or Drop One Character: |
| 16 | # A match extends the diagonal (prev[j - 1] + 1); otherwise drop one of the two last characters. |
| 17 | if text1[i - 1] == text2[j - 1]: |
| 18 | curr[j] = prev[j - 1] + 1 |
| 19 | else: |
| 20 | curr[j] = max(prev[j], curr[j - 1]) |
| 21 | # 2. Roll The Row Forward: |
| 22 | # curr becomes the finished row i; it is read as the row above while filling row i + 1. |
| 23 | prev = curr |
| 24 | |
| 25 | return prev[n] |
i is filled, prev[j] is the answer for text1[:i] and text2[:j] for every j.Let the two axes of the table be the prefixes text1[:i] and text2[:j]. Cell (i, j) depends on three neighbours: the cell above (drop the last character of text1), the cell to the left (drop the last character of text2) and the diagonal cell (use both last characters when they match). Rows are filled in order, so all three are final, and two rolling rows are enough. The trap is the index: row i ends with text1[i - 1], so compare text1[i - 1] == text2[j - 1]; comparing text1[i] reads one character too far.
See it run
Longest Common Subsequence, step by step
i -j -curr[j] -
Row i is the prefix text1[:i]. Column j is the prefix text2[:j]. A cell is the longest common subsequence length of those two prefixes.
newthe cell being writtendiagthe cell one row up and one column left, read on a matchabovethe cell one row up, read on a mismatchleftthe cell one column left, read on a mismatchanswerthe final answer
Start: text1 = "abcde" and text2 = "ace". Row i is the prefix text1[:i]. Column j is the prefix text2[:j].
Gotcha 1 of 3
- The trap
Gotcha 1: Comparing
text1[i]andtext2[j]without the- 1Mistakeif text1[i] == text2[j]:Fixif text1[i - 1] == text2[j - 1]:What happens: The table has an extra row and column for the empty prefix. So row
istands for the prefixtext1[:i], whose last character istext1[i - 1]. In the same way, columnjends withtext2[j - 1].text1[i]andtext2[j]are one character too far. Atj = n,text2[j]reads past the end oftext2.Example: text1 = "abc", text2 = "ab"Mistake: raises IndexErrorFix: returns 2
- You walk right and down through one grid and no second sequence is compared, as in Unique Paths (LC 62): each cell needs only the cell above and the cell to the left. See Grid DP
- You must count how many different ways one string can be picked out of the other, as in Distinct Subsequences (LC 115), not the length or cost of one best alignment. See Distinct Subsequences
Deep Dive
What a cell means when the axes are two strings
Grid DP already taught the table and the row-by-row fill. This card changes what the two axes are. Row i stands for the prefix text1[:i], and column j stands for the prefix text2[:j]. A prefix is the first characters of a string.
The cell (i, j) is the answer for that pair of prefixes. In longest_common_subsequence, it is the length of the longest common subsequence of text1[:i] and text2[:j]. A subsequence keeps the order of characters but may skip characters.
Index 0 on each axis is the empty prefix. These extra cells let the first real character use the same formula as every other character. The number of states is (m + 1) * (n + 1).
Why the recurrence is correct
Look at the last characters text1[i - 1] and text2[j - 1]. If they are equal, some best common subsequence can end with that pair. Taking the pair never loses length, so the answer is prev[j - 1] + 1. The cell on the diagonal is the answer for the two prefixes without those last characters.
If they differ, they cannot both be the last matched pair. At least one of them is not used. So the answer is the better of dropping the last character of text1, which is prev[j], or dropping the last character of text2, which is curr[j - 1].
Example: for text1 = "abcde" and text2 = "ace", the final row is [0, 1, 2, 3], so the answer is 3, the subsequence "ace". If the match case is removed and every cell uses max(prev[j], curr[j - 1]), all cells stay 0, and "abc" against "abc" returns 0 instead of 3.
Why two rows are needed, and what is lost
A match reads the diagonal cell prev[j - 1]. In a single row, row[j - 1] is overwritten by the current row before it is needed as the diagonal. So the code keeps two rows, prev and curr. After the inner loop, prev = curr makes the finished row the row above for the next i.
The code swaps the strings so that text2 is the shorter one. The length of the longest common subsequence does not change when the strings swap places. So each row has min(m, n) + 1 entries.
Rolling rows keep only the last row. You can read the length, but you cannot walk back through the table to print a subsequence. For that, keep the full table.
The cost, and the same shape for Edit Distance
Each cell reads at most three cells and does one comparison. The time is O(M * N). For two strings of length 1000, that is about one million cell updates. The space is O(min(M, N)) for the two rows.
Edit Distance (LC 72) uses the same table. The base cells are not 0. Turning word1[:i] into the empty string takes i deletions, so dp[i][0] = i and dp[0][j] = j. On a match the cell copies the diagonal. On a mismatch it is 1 + min(above, left, diagonal), which stands for a delete, an insert, or a replace. For "horse" and "ros" the answer is 3.
So the work to learn is the meaning of the three neighbours and the base cells. The loops stay the same.
60-Second Pitch
"A brute force tries every subsequence of one string and checks it against the other, which takes exponential time. I define one cell (i, j) as the answer for the first i characters of one string and the first j characters of the other. Each cell depends on the cell above, the cell to the left, and the diagonal cell. If the last characters match, I take the diagonal value plus one. If they differ, I take the larger of the cell above and the cell to the left. There are M times N cells with constant work each, so the time is O(M * N). I keep only two rows of the shorter string's length, so the space is O(min(M, N)). If the problem needs the actual subsequence, I keep the full table and walk back from the last cell."
Common Questions
- How do you print the actual longest common subsequence, not only its length?
Keep the full table, with M + 1 rows and N + 1 columns. Start at the last cell. If the last characters match, add that character to the result and move to the diagonal cell. If not, move to the neighbour with the larger value, the cell above or the cell to the left. Reverse the collected characters at the end. This uses O(M * N) space.
- What are the time and space complexity of
longest_common_subsequence? O(M * N) time, because each of the
(M + 1) * (N + 1)cells does constant work. The space is O(min(M, N)), because the code keeps two rows of the shorter string's length plus one.- Why does the code need two rows when Unique Paths (LC 62) needs one?
A match reads the diagonal cell
prev[j - 1]. In one row, that cell has already been overwritten by the current row. Unique Paths reads only the cell above and the cell to the left, so one row is enough there.- How does Edit Distance (LC 72) differ from this table?
The grid and the three neighbours are the same. The base cells are
iandj, because turning a prefix into the empty string costs one deletion per character. On a match the cell copies the diagonal. On a mismatch it is1 + min(above, left, diagonal). It takes a minimum instead of a maximum.- How does Delete Operation for Two Strings (LC 583) use the same table?
Only the characters in a common subsequence can stay, and every other character is deleted. So the answer is
len(text1) + len(text2) - 2 * lcs, wherelcsis the result oflongest_common_subsequence. For"sea"and"eat"the longest common subsequence has length 2, so the answer is 2.
SWE Reasoning
Spot it
- Two strings or two arrays are compared, aligned, or turned into each other: common subsequence, edit distance, wildcard or pattern matching.
- The answer for a pair of prefixes
(i, j)can be built from the answers for(i - 1, j),(i, j - 1)and(i - 1, j - 1). - The sizes are about 1000 or less on each side, so
M * Ncells is fine, and trying every subsequence is exponential. - The problem asks for one number (a length, a count, a minimum cost), not for every solution listed.
- Counting the number of different ways, as in Distinct Subsequences (LC 115), also fits this table, with a sum in place of a maximum.
The invariant, step by step
- Before the loop,
previs all zeros. It describes the empty prefix oftext1, which has no common subsequence with any prefix oftext2. - At row
i,curr[0]is 0, because an empty prefix oftext2matches nothing. - For each
j, the code comparestext1[i - 1]withtext2[j - 1]. These are the last characters of the two prefixes. - On a match,
curr[j] = prev[j - 1] + 1. The pair extends the best answer for the two shorter prefixes. - On a mismatch,
curr[j] = max(prev[j], curr[j - 1]). One of the two last characters is dropped. - After the inner loop,
prev = curr. Nowprev[j]is the answer fortext1[:i]andtext2[:j]for everyj, which is the card's invariant. The last step returnsprev[n].
Traps
- Compare
text1[i]withtext2[j]. The last character of prefixiistext1[i - 1]. Without the- 1,text2[j]reads past the end atj = nand raisesIndexError. - Read the diagonal from
curr[j - 1]. That is the cell to the left, not the diagonal. One character oftext1can then match twice.longest_common_subsequence("ab", "bb")returns 2 instead of 1. - Use 0 for every base cell. For the longest common subsequence the empty-prefix cells are 0. For Edit Distance (LC 72) they are
iandj. With zero base cells,"horse"to"ros"gives 2 instead of 3. - Drop the match case. With only
max(prev[j], curr[j - 1]), no cell ever grows, and the answer is always 0. - Try to rebuild the answer from rolling rows. The earlier rows are gone. Keep the full table when the problem asks for the sequence or the edit steps.
Practice
Builds on Grid DP, which you haven’t finished yet.
Two-Sequence DP (Longest Common Subsequence, Edit Distance)
You're handed two strings, text1 and text2. A subsequence of a string is whatever remains after deleting zero or more of its characters while keeping the survivors in their original order -- for instance, "ace" can be pulled out of "abcde" this way. A common subsequence is a subsequence the two strings share.
Report the length of the longest subsequence they have in common, or 0 if they share none.
Two-Sequence DP
dp[i][j] = the answer for text1[:i] and text2[:j] ➔ built from the cell above, the cell to the left and the diagonal ➔ 1D rolling row| 1 | def longest_common_subsequence(text1: str, text2: str) -> int: |
| 2 | """Longest Common Subsequence with two rolling rows. |
| 3 | Time: O(M * N) | Space: O(min(M, N)) |
| 4 | """ |
| 5 | if len(text1) < len(text2): |
| 6 | text1, text2 = text2, text1 # text2 is the shorter string |
| 7 | |
| 8 | m, n = len(text1), len(text2) |
| 9 | # prev, curr: two rolling rows of the DP table; index 0 of each row is the empty prefix |
| 10 | prev = [0] * (n + 1) |
| 11 | |
| 12 | for i in range(1, m + 1): |
| 13 | curr = [0] * (n + 1) |
| 14 | for j in range(1, n + 1): |
| 15 | # 1. Extend Or Drop One Character: |
| 16 | # A match extends the diagonal (prev[j - 1] + 1); otherwise drop one of the two last characters. |
| 17 | if text1[i - 1] == text2[j - 1]: |
| 18 | curr[j] = prev[j - 1] + 1 |
| 19 | else: |
| 20 | curr[j] = max(prev[j], curr[j - 1]) |
| 21 | # 2. Roll The Row Forward: |
| 22 | # curr becomes the finished row i; it is read as the row above while filling row i + 1. |
| 23 | prev = curr |
| 24 | |
| 25 | return prev[n] |
i is filled, prev[j] is the answer for text1[:i] and text2[:j] for every j.Let the two axes of the table be the prefixes text1[:i] and text2[:j]. Cell (i, j) depends on three neighbours: the cell above (drop the last character of text1), the cell to the left (drop the last character of text2) and the diagonal cell (use both last characters when they match). Rows are filled in order, so all three are final, and two rolling rows are enough. The trap is the index: row i ends with text1[i - 1], so compare text1[i - 1] == text2[j - 1]; comparing text1[i] reads one character too far.
See it run
Longest Common Subsequence, step by step
i -j -curr[j] -
Row i is the prefix text1[:i]. Column j is the prefix text2[:j]. A cell is the longest common subsequence length of those two prefixes.
newthe cell being writtendiagthe cell one row up and one column left, read on a matchabovethe cell one row up, read on a mismatchleftthe cell one column left, read on a mismatchanswerthe final answer
Start: text1 = "abcde" and text2 = "ace". Row i is the prefix text1[:i]. Column j is the prefix text2[:j].
Gotcha 1 of 3
- The trap
Gotcha 1: Comparing
text1[i]andtext2[j]without the- 1Mistakeif text1[i] == text2[j]:Fixif text1[i - 1] == text2[j - 1]:What happens: The table has an extra row and column for the empty prefix. So row
istands for the prefixtext1[:i], whose last character istext1[i - 1]. In the same way, columnjends withtext2[j - 1].text1[i]andtext2[j]are one character too far. Atj = n,text2[j]reads past the end oftext2.Example: text1 = "abc", text2 = "ab"Mistake: raises IndexErrorFix: returns 2
- You walk right and down through one grid and no second sequence is compared, as in Unique Paths (LC 62): each cell needs only the cell above and the cell to the left. See Grid DP
- You must count how many different ways one string can be picked out of the other, as in Distinct Subsequences (LC 115), not the length or cost of one best alignment. See Distinct Subsequences
Deep Dive
What a cell means when the axes are two strings
Grid DP already taught the table and the row-by-row fill. This card changes what the two axes are. Row i stands for the prefix text1[:i], and column j stands for the prefix text2[:j]. A prefix is the first characters of a string.
The cell (i, j) is the answer for that pair of prefixes. In longest_common_subsequence, it is the length of the longest common subsequence of text1[:i] and text2[:j]. A subsequence keeps the order of characters but may skip characters.
Index 0 on each axis is the empty prefix. These extra cells let the first real character use the same formula as every other character. The number of states is (m + 1) * (n + 1).
Why the recurrence is correct
Look at the last characters text1[i - 1] and text2[j - 1]. If they are equal, some best common subsequence can end with that pair. Taking the pair never loses length, so the answer is prev[j - 1] + 1. The cell on the diagonal is the answer for the two prefixes without those last characters.
If they differ, they cannot both be the last matched pair. At least one of them is not used. So the answer is the better of dropping the last character of text1, which is prev[j], or dropping the last character of text2, which is curr[j - 1].
Example: for text1 = "abcde" and text2 = "ace", the final row is [0, 1, 2, 3], so the answer is 3, the subsequence "ace". If the match case is removed and every cell uses max(prev[j], curr[j - 1]), all cells stay 0, and "abc" against "abc" returns 0 instead of 3.
Why two rows are needed, and what is lost
A match reads the diagonal cell prev[j - 1]. In a single row, row[j - 1] is overwritten by the current row before it is needed as the diagonal. So the code keeps two rows, prev and curr. After the inner loop, prev = curr makes the finished row the row above for the next i.
The code swaps the strings so that text2 is the shorter one. The length of the longest common subsequence does not change when the strings swap places. So each row has min(m, n) + 1 entries.
Rolling rows keep only the last row. You can read the length, but you cannot walk back through the table to print a subsequence. For that, keep the full table.
The cost, and the same shape for Edit Distance
Each cell reads at most three cells and does one comparison. The time is O(M * N). For two strings of length 1000, that is about one million cell updates. The space is O(min(M, N)) for the two rows.
Edit Distance (LC 72) uses the same table. The base cells are not 0. Turning word1[:i] into the empty string takes i deletions, so dp[i][0] = i and dp[0][j] = j. On a match the cell copies the diagonal. On a mismatch it is 1 + min(above, left, diagonal), which stands for a delete, an insert, or a replace. For "horse" and "ros" the answer is 3.
So the work to learn is the meaning of the three neighbours and the base cells. The loops stay the same.
60-Second Pitch
"A brute force tries every subsequence of one string and checks it against the other, which takes exponential time. I define one cell (i, j) as the answer for the first i characters of one string and the first j characters of the other. Each cell depends on the cell above, the cell to the left, and the diagonal cell. If the last characters match, I take the diagonal value plus one. If they differ, I take the larger of the cell above and the cell to the left. There are M times N cells with constant work each, so the time is O(M * N). I keep only two rows of the shorter string's length, so the space is O(min(M, N)). If the problem needs the actual subsequence, I keep the full table and walk back from the last cell."
Common Questions
- How do you print the actual longest common subsequence, not only its length?
Keep the full table, with M + 1 rows and N + 1 columns. Start at the last cell. If the last characters match, add that character to the result and move to the diagonal cell. If not, move to the neighbour with the larger value, the cell above or the cell to the left. Reverse the collected characters at the end. This uses O(M * N) space.
- What are the time and space complexity of
longest_common_subsequence? O(M * N) time, because each of the
(M + 1) * (N + 1)cells does constant work. The space is O(min(M, N)), because the code keeps two rows of the shorter string's length plus one.- Why does the code need two rows when Unique Paths (LC 62) needs one?
A match reads the diagonal cell
prev[j - 1]. In one row, that cell has already been overwritten by the current row. Unique Paths reads only the cell above and the cell to the left, so one row is enough there.- How does Edit Distance (LC 72) differ from this table?
The grid and the three neighbours are the same. The base cells are
iandj, because turning a prefix into the empty string costs one deletion per character. On a match the cell copies the diagonal. On a mismatch it is1 + min(above, left, diagonal). It takes a minimum instead of a maximum.- How does Delete Operation for Two Strings (LC 583) use the same table?
Only the characters in a common subsequence can stay, and every other character is deleted. So the answer is
len(text1) + len(text2) - 2 * lcs, wherelcsis the result oflongest_common_subsequence. For"sea"and"eat"the longest common subsequence has length 2, so the answer is 2.
SWE Reasoning
Spot it
- Two strings or two arrays are compared, aligned, or turned into each other: common subsequence, edit distance, wildcard or pattern matching.
- The answer for a pair of prefixes
(i, j)can be built from the answers for(i - 1, j),(i, j - 1)and(i - 1, j - 1). - The sizes are about 1000 or less on each side, so
M * Ncells is fine, and trying every subsequence is exponential. - The problem asks for one number (a length, a count, a minimum cost), not for every solution listed.
- Counting the number of different ways, as in Distinct Subsequences (LC 115), also fits this table, with a sum in place of a maximum.
The invariant, step by step
- Before the loop,
previs all zeros. It describes the empty prefix oftext1, which has no common subsequence with any prefix oftext2. - At row
i,curr[0]is 0, because an empty prefix oftext2matches nothing. - For each
j, the code comparestext1[i - 1]withtext2[j - 1]. These are the last characters of the two prefixes. - On a match,
curr[j] = prev[j - 1] + 1. The pair extends the best answer for the two shorter prefixes. - On a mismatch,
curr[j] = max(prev[j], curr[j - 1]). One of the two last characters is dropped. - After the inner loop,
prev = curr. Nowprev[j]is the answer fortext1[:i]andtext2[:j]for everyj, which is the card's invariant. The last step returnsprev[n].
Traps
- Compare
text1[i]withtext2[j]. The last character of prefixiistext1[i - 1]. Without the- 1,text2[j]reads past the end atj = nand raisesIndexError. - Read the diagonal from
curr[j - 1]. That is the cell to the left, not the diagonal. One character oftext1can then match twice.longest_common_subsequence("ab", "bb")returns 2 instead of 1. - Use 0 for every base cell. For the longest common subsequence the empty-prefix cells are 0. For Edit Distance (LC 72) they are
iandj. With zero base cells,"horse"to"ros"gives 2 instead of 3. - Drop the match case. With only
max(prev[j], curr[j - 1]), no cell ever grows, and the answer is always 0. - Try to rebuild the answer from rolling rows. The earlier rows are gone. Keep the full table when the problem asks for the sequence or the edit steps.