The problem
Given two strings, return the length of their longest common subsequence: the longest sequence of letters that appears in both, in the same order (letters don’t have to be next to each other).
Input: "abcde" and "ace"
Output: 3 ("ace")Picture it
Picture two DNA strands written along the top and side of a table. Cell (i, j) answers: “how long is the longest match using the first i letters of A and the first j letters of B?” If the letters at i and j are the same, the answer is the diagonal cell + 1 (we pair them up). If they differ, we drop a letter from one strand or the other and take the better: the cell above or the cell to the left.
How to recognise it
- You compare two sequences and want the longest thing they share in order.
- The letters need not be next to each other: this is a subsequence, not a substring.
- Deciding about the last letters of both strings leaves the same question on shorter prefixes.
- Lengths up to 1000 each make trying every subsequence impossible.
- The answer is a number, not the subsequence itself, so a table of lengths is enough.
Start with brute force
Try every subsequence of the first string (keep or drop each letter) and test whether it also appears, in order, inside the second string. Keep the longest.
def lcs_brute(a, b):
best = 0
n = len(a)
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]
it = iter(b)
if all(ch in it for ch in sub): # each letter found after the previous one
best = max(best, len(sub))
return best
There are 2^m subsets of the first string, and each test scans the second string, so time is about O(2^m · (m + n)). With m = 1000 that is more than 10^300 subsets. Space is O(m).
From brute force to the idea
- Look at the last letters. Compare the final letter of each prefix,
a[i-1]andb[j-1]. - If they match, some best common subsequence can use both as its last letter, so the answer is 1 plus the answer for the two shorter prefixes:
t[i-1][j-1] + 1. - If they differ, at least one of them is not used, so drop one and keep the better result:
max(t[i-1][j], t[i][j-1]). - Build a table.
t[i][j]is the answer for the first i letters ofaand the first j letters ofb. Row 0 and column 0 are 0, because an empty string shares nothing. - Fill row by row. Each cell needs only the cell above, the cell on the left and the diagonal, which are all finished already. The bottom-right cell is the answer.
This is the key idea: the answer for two prefixes comes from one of three smaller prefix pairs, so each of the m · n pairs is solved once.
The key idea
dp[i][j] = dp[i−1][j−1] + 1 if A[i] == B[j], else max(dp[i−1][j], dp[i][j−1]). O(m × n).
Python solution
def lcs(a, b):
t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
t[i][j] = t[i - 1][j - 1] + 1 # letters pair up
else:
t[i][j] = max(t[i - 1][j], t[i][j - 1])
return t[len(a)][len(b)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(2^m · (m + n)): every subset of the first string is tested | O(m): one subset |
| DP table (shown code) | O((m + 1)(n + 1)) = O(m · n): one constant-time step per cell | O(m · n): the full table; keeping two rows would give O(n) |
For two strings of length 1000 that is about one million cells.
Edge cases
- Either string empty: the loops do nothing and the code returns 0 (
lcs("", "abc")). - No letters in common (
"abc","def"): returns 0. - Identical strings: returns the length (
"abc","abc"gives 3). - Repeated letters (
"aaaa","aa"): returns 2, since the shorter string is a subsequence of the longer one. - Order matters:
"abcde"and"ace"give 3, but"abc"against"cba"gives 1, because only one letter can keep its order. - Symmetry: swapping the arguments never changes the answer.
Common mistakes
- Mixing up substring and subsequence, and only extending the diagonal (that solves "longest common substring", a different problem).
- Indexing
a[i]instead ofa[i - 1], because the table has one extra row and column. - On a mismatch, taking only the diagonal instead of the maximum of above and left.
- Returning
t[-1]or the maximum of the last row, instead of the bottom-right cell.
Given two strings, return the length of the shortest string that has both as subsequences. For "abac" and "cab" the answer is 5 (for example "cabac"). Describe your approach, then write it if you like.
Compare with our answer
Every letter of the shortest supersequence is either shared or belongs to only one string. The shared letters can be merged once, and they are best chosen as the longest common subsequence, so the length is m + n minus the LCS.
def shortest_supersequence_length(a, b):
return len(a) + len(b) - lcs(a, b) # lcs is the shown function
shortest_supersequence_length("abac", "cab") is 4 + 3 − 2 = 5, and for two strings with nothing in common it is simply m + n. Time O(m · n), space O(m · n).
A strong answer mentions: reusing the LCS table, subtracting the shared letters once, and the case with no shared letters.
1. You need the minimum number of deletions (from both strings) to make two strings equal. Which approach fits best?
The letters that remain must be a common subsequence, so keeping the longest one minimises deletions: m + n − 2 · LCS. Comparing position by position fails when a deleted letter shifts everything after it.
2. Why does the shown code take O(m · n) time while the brute force takes O(2^m (m + n))?
There are (m + 1)(n + 1) prefix pairs and each is computed from three neighbours. The brute force instead tests every subset of the first string.
3. The mismatch line is changed to t[i][j] = t[i - 1][j - 1], so a mismatch copies the diagonal. What does lcs("abc", "abc") and lcs("ab", "ba") give?
For "abc" every pair on the diagonal matches, so it still gives 3. For "ab" and "ba" the last cell compares b with a, mismatches, and copies the diagonal cell, which is 0. The code returns 0 where the right answer is 1.
Score 60% or more and the lesson is marked complete.