1143. Longest Common Subsequence¶
Edited by Charles
Medium · Python · Dynamic Programming
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
Given two strings text1 and text2, return the length of their Longest Common Subsequence (LCS).
A subsequence is obtained by deleting some (or no) characters from a string without changing the relative order of the remaining characters.
Original study notes follow, including intermediate snippets and earlier attempts.
Idea¶
Given two strings text1 and text2, return the length of their Longest Common Subsequence (LCS).
A subsequence is obtained by deleting some (or no) characters from a string without changing the relative order of the remaining characters.
Unlike the Longest Common Subarray problem, the matched characters do not need to be contiguous.
For example:
The longest common subsequence is:
Therefore, the answer is 3.
Dynamic Programming¶
State Definition¶
Let
denote:
The length of the longest common subsequence between
text1[:i]andtext2[:j].
Unlike the Longest Common Subarray problem, dp[i][j] does not require the subsequence to end at text1[i-1] and text2[j-1].
Initialization¶
If either string is empty, there is no common subsequence.
Therefore, initialize the first row and first column to 0.
The extra row and column eliminate boundary checks.
State Transition¶
Case 1: Current characters match¶
If
the current characters can be included in the longest common subsequence.
Update:
Case 2: Current characters do not match¶
If the current characters are different, at least one of them cannot belong to the LCS.
There are two possibilities:
- Ignore the current character in
text1 - Ignore the current character in
text2
Take the better result:
Transition equation:
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])
The key idea is:
If the current characters match, include them in the LCS. Otherwise, discard one character and keep the longer subsequence.
Final Answer¶
Since dp[i][j] represents the LCS length between the prefixes text1[:i] and text2[:j], the final answer is
which is equivalent to
Example¶
Initialization:
Match 'a'¶
Update:
Compare 'b' and 'c'¶
Choose the larger value:
Match 'c'¶
Update:
Match 'e'¶
Update:
Final answer:
Complexity Analysis¶
Time Complexity
where
m = len(text1)n = len(text2)
Each state is computed exactly once.
Space Complexity
A 2D DP table is required.
Note: The DP table can be optimized to O(n) using a rolling array because each state only depends on the previous row and the current row.
Summary¶
State Definition
Initialization
State Transition
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])
Traversal Order
Traverse both strings from left to right while filling the DP table.
Final Answer
Common Mistakes¶
- Do not confuse this problem with Longest Common Subarray (LeetCode 718).
- Longest Common Subarray: elements must be contiguous.
- Longest Common Subsequence: elements only need to preserve their relative order.
-
When the current characters do not match, do not reset the state to
0.Instead,
because previously matched subsequences can still be extended later.
dp[i][j]represents the LCS length between two prefixes, not the LCS ending at the current characters.- The answer is directly stored in
There is no need to maintain a separate global maximum.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
Python solution¶
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
l1 = len(text1)
l2 = len(text2)
dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]
for i in range(1, l1 + 1):
for j in range(1, l2 + 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[-1][-1]