Delete Operation for Two Strings
Delete Operation for Two Strings: minimum deletions from two strings to make them equal.
- 1 <= word1.length, word2.length <= 500
- word1 and word2 consist of only lowercase English letters.
Intuition
Delete operation for two strings finds the minimum number of character deletions, from either string, needed to make them equal. Deletions are the only permitted operation.
Thinking about which characters to delete is the hard way round. The characters that survive are far more informative: whatever remains must appear in both strings in the same relative order, which is precisely a common subsequence.
Deleting as little as possible means keeping as much as possible, so:
- Find the longest common subsequence, then delete everything else — the answer is m + n − 2 × LCS.
The factor of 2 catches people out. The LCS is retained in both strings, so it must be subtracted from each length independently. Subtracting it once counts the shared portion as saved from only one string.
The LCS itself is the standard DP. When characters match, dp[i][j] = dp[i-1][j-1] + 1 — both are consumed and the match extends the subsequence. When they differ, dp[i][j] = max(dp[i-1][j], dp[i][j-1]), skipping one character from either string and keeping the better result.
The base row and column are 0, since a subsequence shared with an empty string has no length.
An alternative computes the deletion count directly, with dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 on a mismatch. It is equally valid, but routing through LCS reuses a pattern that solves many problems rather than a formula specific to this one.
Deletions only, so whatever survives must appear in both strings in order — that's the longest common subsequence. The answer is m + n - 2·lcs: everything outside the LCS gets deleted from one side or the other.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(m*n) time and O(m*n) space.
Think about what survives
Rather than choosing deletions, ask what remains. The surviving characters must appear in both strings in the same order — that is a common subsequence by definition.
Maximise what is kept
Minimum deletions means maximum retention, so the goal is the longest common subsequence. This converts the problem into a well-known one.
Build the LCS table
dp[i][j] is the LCS length of the first i and j characters. Base row and column are 0, since nothing is shared with an empty string.
Extend on a character match
When characters match, dp[i][j] = dp[i-1][j-1] + 1 — both are consumed and the match lengthens the subsequence.
Take the better skip on a mismatch
When they differ, dp[i][j] = max(dp[i-1][j], dp[i][j-1]), skipping a character from one string or the other and keeping the larger result.
Apply the formula with the factor of two
The answer is m + n - 2 * LCS. The subsequence is kept in both strings, so it must be subtracted from each length — subtracting once is the classic error.
Cost of the tabulation
Every cell is filled once with O(1) work, giving O(m · n) time and O(m · n) space, reducible to O(min(m, n)) with a rolling row.
Solution & live demo
Common pitfalls
Subtracting the LCS once
return m + n - lcs
return m + n - 2 * lcs
The common subsequence is preserved in both strings, so it must be excluded from both deletion counts. Subtracting once leaves the LCS length counted as deletions on one side.
Using edit distance
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Edit distance allows substitution and insertion, which this problem forbids — only deletions are permitted. The LCS recurrence takes a max rather than a min and has no diagonal-replace case.
Comparing with the wrong index offset
if word1[i] == word2[j]:
if word1[i - 1] == word2[j - 1]:
The table is 1-indexed so that row 0 and column 0 hold the empty-prefix base cases. Reading the strings at i rather than i-1 compares the wrong characters and runs off the end.
Edge cases
LCS is 0, so the answer is simply the length of the non-empty string, matching that every character in it must be deleted.
LCS equals the full length of either string, giving 0 deletions.
LCS is 0, so the answer is len(word1) + len(word2), meaning both strings get fully deleted.
LCS equals the shorter string's length, so only the longer string's extra characters need deleting.