The problem
A subsequence keeps some characters of a string in order, not necessarily next to each other: ace is one of abcde. Given text1 and text2, return the length of the longest subsequence they share, or 0 if none.
Examples
- Input
text1 = "abcde", text2 = "ace"
- Output
3
- Input
text1 = "abc", text2 = "abc"
- Output
3
- Input
text1 = "abc", text2 = "def"
- Output
0
Constraints
- 1 ≤ text1.length, text2.length ≤ 1000
- Only lowercase English letters.
The idea
Let lcs(i, j) be the answer for the first i letters of text1 and the first j of text2. If their last letters match, both can end the common subsequence: 1 + lcs(i − 1, j − 1). If not, at least one of them is unused: max(lcs(i − 1, j), lcs(i, j − 1)).
That fills a table row by row, each cell from the one above, the one to the left and the one diagonally up-left. Only the previous row is ever read, so one row, overwritten in place, is enough — with the up-left value saved before it is overwritten.
- Time
- O(m · n)
- Space
- O(n) — one row
Solution · every language run against every case
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: # lcs(i, j) for the first i letters of text1 and j of text2: if the last letters match, # 1 + lcs(i - 1, j - 1); otherwise drop one of them, max(lcs(i - 1, j), lcs(i, j - 1)). # One row at a time is enough. row = [0] * (len(text2) + 1) for a in text1: diag = 0 # lcs(i - 1, j - 1): the old row's value one to the left for j in range(1, len(text2) + 1): above = row[j] row[j] = diag + 1 if a == text2[j - 1] else max(row[j], row[j - 1]) diag = above return row[-1]