Problem overview
The method longestCommonSubsequence receives two strings, text1 and text2, and returns the length of their longest common subsequence. A subsequence is what remains after deleting some characters, possibly none, without reordering the rest. "ace" is a subsequence of "abcde", but "aec" is not. A common subsequence is a subsequence of both strings. Only the length is returned, and it is 0 when the strings share no character. Both strings have 1 to 1000 lowercase letters, and the statement asks for O(n · m) time and space.
For "abcde" and "ace" the answer is 3, from "ace". For "abc" and "def" it is 0.
Approach: solve every pair of prefixes
A string of 1000 characters has up to 2 to the power of 1000 subsequences, so comparing them all is out of the question. Instead, solve smaller versions. Let dp[i][j] be the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2. The answer is dp[n][m], where n and m are the string lengths.
Look at the last characters of the two prefixes, text1[i - 1] and text2[j - 1]:
- They are equal. Then
dp[i][j] = dp[i - 1][j - 1] + 1. Adding the shared character to the best answer for the shorter prefixes reaches that length, and nothing does better: removing the last character of any common subsequence leaves a common subsequence of the two shorter prefixes. - They differ. A common subsequence can't end with both characters, so it leaves out at least one. Then
dp[i][j]is the larger ofdp[i - 1][j](without the last character oftext1) anddp[i][j - 1](without the last character oftext2).
Row 0 and column 0 stand for an empty prefix, which has nothing in common with anything, so they stay 0.
Step by step
- Store the lengths:
n = len(text1)andm = len(text2). Both come up often. - Create the table with
n + 1rows, each a new list ofm + 1zeros, using a list comprehension. The extra row and column are the empty prefixes. The name_says the loop variable isn't used. - Loop
ioverrange(1, n + 1), one row per prefix oftext1. Row 0 already holds zeros. - Loop
joverrange(1, m + 1)inside it. Filling row by row and left to right means the entries above, to the left and diagonally up-left are known whendp[i][j]is computed. - Equal last characters: if
text1[i - 1] == text2[j - 1], setdp[i][j]todp[i - 1][j - 1] + 1. The firsticharacters end at indexi - 1, because the string counts from 0 while the table counts characters. - Different last characters: in the
else, setdp[i][j]tomax(dp[i - 1][j], dp[i][j - 1]). - Return
dp[n][m], the answer for both whole strings.
The solution in Python
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n = len(text1)
m = len(text2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
For "abcde" and "ace" the finished table has one row per prefix of "abcde", starting with the empty prefix:
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]
The columns go with the prefixes "", "a", "ac" and "ace". The bottom-right entry, 3, is the answer.
Python details worth knowing:
- Build the rows with a comprehension.
[[0] * (m + 1)] * (n + 1)repeats one row object, so changing one row changes them all. Withn = 5andm = 3, settingdp[1][1] = 7on that table changes the second entry of every row. The comprehension creates a separate list for each row. - Negative indexes don't raise errors.
dp[-1]is the last row. The loops start at 1, soi - 1andj - 1are never negative, but a loop starting at 0 would silently read the wrong cells. - Strings index by character.
text1[i - 1]is a one-character string, and==compares contents.
Complexity
Time: O(n · m): the table has (n + 1) × (m + 1) entries, and each takes constant work. Space: O(n · m) for the table. Each row reads only itself and the row above, so two rows of m + 1 numbers would bring the space down to O(m). The lesson keeps the whole table, which is easier to follow.
Edge cases and common mistakes
- No common character.
"abc"and"def"give 0. - Identical strings.
"abc"and"abc"give 3. - Repeated letters.
"aaa"and"aa"give 2. - Order matters.
"ace"and"aec"give 2, not 3, since the characters must keep their order."abc"and"cba"give 1. - Off-by-one indexing. Using
text1[i]instead oftext1[i - 1]raises anIndexErroron the last row or column, or compares the wrong characters. - Subsequence versus substring. A substring must be contiguous; a subsequence may skip characters.
Testing
"abcde","ace"gives3."abcbdab","bdcaba"gives4."abc","def"gives0."abc","abc"gives3."aaa","aa"gives2."abc","cba"gives1.
