Domain 2MediumCORE

Delete Operation for Two Strings

We are given two strings, word1 and word2. The goal is to make them identical using only deletion operations on either string. We need to return the minimum number of deletions required.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String

583. Delete Operation for Two Strings

Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 50.4%


Problem Breakdown

We are given two strings, word1 and word2. The goal is to make them identical using only deletion operations on either string. We need to return the minimum number of deletions required.

  • Inputs: Two lowercase English letter strings (word1, word2). Lengths between 1 and 500.
  • Output: An integer representing the total count of characters deleted from both strings combined.
  • Implicit Logic: To minimize deletions, we must maximize the number of characters kept. The set of kept characters in both strings will form a common subsequence. Therefore, this problem is mathematically equivalent to finding the Longest Common Subsequence (LCS) and calculating how many characters remain outside that sequence.

Intuition

A brute-force approach would be trying every possible combination of deletions from word1 against every deletion pattern in word2. This leads to an exponential time complexity, which is unacceptable for strings up to length 500 (potentially O(2N)O(2^{N})).

The key insight here is that we don’t need to track the specific characters deleted. Instead, if two characters match at indices (i, j) in our DP state and are part of a common subsequence, we keep them. If they don’t match or aren’t aligned optimally, one must be removed from consideration for this path.

This structure strongly suggests Dynamic Programming (DP). We want to find the length of the Longest Common Subsequence between word1 and word2. Once we know that length (LCS_len), every character in both strings not part of this subsequence must be deleted. The formula becomes: (len(word1) - LCS_len) + (len(word2) - LCS_len), which simplifies to m + n - 2 * lcs_length.

Approach

We will use a 2D DP table where dp[i][j] represents the length of the Longest Common Subsequence between the first i characters of word1 and the first j characters of word2.

Algorithm Steps:

  1. Initialize a matrix (m + 1) x (n + 1) with zeros, where m is len(word1) and n is len(word2). The extra row/column handles base cases for empty prefixes.
  2. Iterate through each character of both strings using nested loops (i from 0 to m-1 in string terms, or 1 to m in DP table rows).
  3. Recurrence Relation:
    • If word1[i - 1] == word2[j - 1]: The characters match and extend the common subsequence found previously. Set dp[i][j] = dp[i - 1][j - 1] + 1.
    • Else: We cannot use both characters simultaneously in this specific alignment. Take the maximum result from either skipping a character in word1 (dp[i-1][j]) or skipping one in word2 (dp[i][j-1]). Set dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
  4. After filling the table, retrieve the LCS length from dp[m][n].
  5. Calculate total deletions using the formula derived in Intuition.

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n) where mm and nn are lengths of the input strings. We visit every cell in the DP table exactly once, performing constant work per cell. With max length 500, operations ≈250,000\approx 250,000, which fits well within time limits (typically ~10^8 ops/sec).
  • Space Complexity: O(m×n)O(m \times n) for the DP matrix. Given constraints (N=500N=500), this is roughly 250KB of memory, which is negligible compared to typical heap sizes.

Solution

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # dp[i][j] stores the length of LCS between word1[:i] and word2[:j]
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                # Characters match: extend the LCS from previous diagonal state
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # Characters don't match: take max of excluding current char 
                # from either word1 or word2 (left or top neighbor)
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    lcs_length = dp[m][n]
    
    # Total deletions is total characters minus the ones we kept in LCS
    return m + n - (2 * lcs_length)

Edge Cases Handled

  • No Common Characters: If word1 and word2 share no common subsequence, lcs_length will be 0. The function correctly returns the sum of both lengths (m + n).
  • Identical Strings: If strings are identical, LCS length equals string length. Result is (len - len) * 2 = 0, which is correct (no steps needed).
  • Different Lengths: The DP table dimensions handle different m and n naturally without index errors due to the offset initialization (+1).
  • Constraint Bounds: While constraints state lengths ≥1\ge 1, the logic holds for length 0 if passed, as loops simply won’t execute or will return base case values correctly.