LeetCode #583 Medium

Delete Operation for Two Strings

Minimum deletions from two strings to make them equal.

dynamic-programmingstringslcs

02

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.

03

Approach

1

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]).

2

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.

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def minDistance(self, word1: str, word2: str) -> int:
▶3        m, n = len(word1), len(word2)
▶4        dp = [[0] * (n + 1) for _ in range(m + 1)]
▶5        for i in range(1, m + 1):
▶6            for j in range(1, n + 1):
▶7                if word1[i - 1] == word2[j - 1]:
▶8                    dp[i][j] = dp[i - 1][j - 1] + 1
▶9                else:
▶10                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
▶11        lcs = dp[m][n]
▶12        return m + n - 2 * lcs

05

Edge cases

One string empty

LCS is 0, so the answer is simply the length of the non-empty string, matching that every character in it must be deleted.

Identical strings

LCS equals the full length of either string, giving 0 deletions.

No characters in common at all

LCS is 0, so the answer is len(word1) + len(word2), meaning both strings get fully deleted.

One string a subsequence of the other

LCS equals the shorter string's length, so only the longer string's extra characters need deleting.

06

Complexity

Time

O(m*n)

Space

O(m*n)

Standard LCS table; reducible to O(min(m,n)) with row rolling.