Problem Breakdown
We are asked to find the length of the longest string that appears as a subsequence in both input strings (text1 and text2). A key distinction here is “subsequence” versus “substring”: characters must maintain their relative order but do not need to be contiguous.
Inputs: Two strings, text1 and text2.
Output: An integer representing the maximum length of a common subsequence (0 if none exists).
Constraints & Edge Cases:
- Lengths are between 1 and 1000. This suggests an solution is acceptable ( operations), but we must be mindful of memory usage for the DP table.
- Characters are lowercase English letters only (no special handling needed for unicode or symbols).
- While constraints say lengths , a robust algorithm should logically handle empty strings by returning 0, which our initialization naturally supports.
Intuition
If we try to solve this recursively without optimization, we would explore every possible combination of characters from text1 and check if they exist in text2. This leads to an exponential time complexity because the same subproblems (calculating LCS for specific prefixes) get recalculated repeatedly.
The core insight is that this problem exhibits optimal substructure and overlapping subproblems. The decision at any point depends on whether characters match or not:
- If
text1[i] == text2[j], we can extend the LCS found so far by adding one character to it. - If they don’t match, we must skip either
text1[i]ortext2[j]. The result is the maximum of these two choices.
This structure maps perfectly onto a Dynamic Programming (DP) table where each cell represents the LCS length for specific prefixes of both strings.
Approach
We will construct a 2D DP matrix, dp, with dimensions (len(text1) + 1) by (len(text2) + 1). The extra row and column represent empty prefix cases (base case), which always have an LCS length of 0.
Algorithm Steps:
- Initialize the DP table filled with zeros.
- Iterate through each character index
ifortext1andjfortext2. - Match Case: If characters match (
text1[i] == text2[j]), thendp[i+1][j+1] = dp[i][j] + 1. We take the diagonal value (representing LCS of previous prefixes) and increment it because we found a common character to extend that subsequence. - Mismatch Case: If characters do not match, we cannot form an extension using this specific pair. The best result is
max(dp[i][j+1], dp[i+1][j]). This means either skipping the current char intext2or skipping the current char intext1, whichever yields a longer subsequence found previously. - After filling the table, return the value at
dp[len(text1)][len(text2)].
Complexity Analysis
- Time Complexity: , where and are lengths of
text1andtext2. We visit every cell in the DP matrix exactly once. Given constraints up to 1000 characters, this is roughly operations, which fits well within typical time limits (usually ~1 second for ops). - Space Complexity: for the DP table. With lengths of 1000, we allocate approximately 4MB of memory (assuming integers), which is negligible compared to standard heap limits.
Solution
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
# Initialize DP table with (m+1) rows and (n+1) columns.
# dp[i][j] stores the LCS length for text1[:i] and text2[:j].
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Iterate through both strings using indices i and j.
# We use ranges up to m/n because we access dp[i+1][j+1],
# effectively processing the character at text1[i].
for i, char1 in enumerate(text1):
for j, char2 in enumerate(text2):
if char1 == char2:
# Characters match. Extend the LCS from previous diagonal state + 1.
dp[i+1][j+1] = dp[i][j] + 1
else:
# Characters mismatch. Take max of skipping current char in either string.
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
return dp[m][n]