Delete Operation for Two Strings
Minimum deletions from two strings to make them equal.
Open on LeetCode ↗Intuition
The trap is diving in to design a brand new edit-distance-style DP from scratch, tracking deletion costs directly in a fresh recurrence. Stop and reframe instead: only deletions are allowed here, no replacements or insertions, which means whatever characters you end up KEEPING in both strings must already form a common subsequence, and the longest possible one to keep is the LCS. Once you see that, the answer is just len(word1) + len(word2) - 2*LCS(word1, word2): every character not in that shared subsequence has to be deleted out of its own word. Recognizing the reduction to a problem you already know how to solve IS the entire problem.
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
Compute the LCS length
Build the standard dp table where dp[i][j] is the LCS length of word1[:i] and word2[:j]: dp[i][j] = dp[i-1][j-1] + 1 when the characters match, otherwise max(dp[i-1][j], dp[i][j-1]).
Apply the deletion formula
Once dp[m][n] holds the LCS length, the minimum deletions is len(word1) + len(word2) - 2 * dp[m][n]: each word individually deletes exactly the characters that fall outside the shared subsequence.
Why this is optimal
Any valid transformation that makes the two words equal via deletion-only operations must leave behind a string that is a subsequence of both originals, so the longest such leftover is exactly the LCS, and maximizing what's kept minimizes what's deleted.
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.