Delete Operation for Two Strings

LeetCode 583: Delete Operation for Two Strings Solution & Explanation

Problem Overview

TL;DR: Use 2D Dynamic Programming to compute the minimum edit distance where the only allowed operation is deletion.

The Delete Operation for Two Strings problem asks us to find the minimum number of steps required to make two provided strings, word1 and word2, identical. A single step consists of deleting exactly one character from either string. This is a minimization problem on strings, making it a classic candidate for optimization algorithms. The solution for LeetCode 583 serves as an excellent introduction to sequence alignment problems found in computational biology and text processing.

Brute Force Approach for Delete Operation for Two Strings

The brute force approach attempts to solve the problem using simple recursion. At any point, comparing the current characters of word1 and word2, we have two main choices if the characters do not match: either delete the character from word1 or delete the character from word2. We explore both possibilities and take the minimum.

Pseudo-code:

function solve(i, j):
    // Base cases: if one string is empty, delete all chars of the other
    if i == length(word1): return length(word2) - j
    if j == length(word2): return length(word1) - i
    
    if word1[i] == word2[j]:
        return solve(i + 1, j + 1) // No deletion needed
    else:
        // Try deleting from word1 or word2, take minimum + 1 cost
        return 1 + min(solve(i + 1, j), solve(i, j + 1))

Time Complexity: $O(2^{\max(M, N)})$ where $M$ and $N$ are the lengths of the strings. In the worst case (no matching characters), the recursion tree branches twice at every step. Why it fails: This approach fails due to Time Limit Exceeded (TLE). The recursion repeatedly solves the same subproblems (e.g., calculating the cost for the suffixes starting at specific indices multiple times). Given the constraint lengths of up to 500, an exponential solution is computationally infeasible.

Algorithm Strategy: DP - 2D Array (Edit Distance)

1. State Definition: Create a 2D array dp of size (m + 1) x (n + 1), where m and n are lengths of word1 and word2. dp[i][j] stores the minimum deletions required to equate word1[0...i-1] and word2[0...j-1].

2. Initialization (Base Cases):

   • dp[0][0] = 0: Two empty strings require 0 deletions.
   • dp[i][0] = i: Transforming word1 of length i to an empty string requires i deletions.
   • dp[0][j] = j: Transforming an empty string to word2 of length j requires j deletions.

3. Iteration:

   • Iterate i from 1 to m.
   • Iterate j from 1 to n.
   • Apply the transition logic derived in the Core Insight section based on character equality.

4. Result: The value at dp[m][n] contains the answer for the full strings.

Execution Flow

Consider word1 = "sea" and word2 = "eat". Dimensions: dp[4][4] (indices 0 to 3).

1. Initialize Boundaries:

   • Row 0: [0, 1, 2, 3] (Deleting "e", "ea", "eat" to match empty "")
   • Col 0: [0, 1, 2, 3] (Deleting "s", "se", "sea" to match empty "")

2. Process "s" (row 1) vs "e", "a", "t":

   • 's' != 'e': min(dp[0][1], dp[1][0]) + 1 = min(1, 1) + 1 = 2.
   • 's' != 'a': min(dp[0][2], dp[1][1]) + 1 = min(2, 2) + 1 = 3.
   • 's' != 't': min(dp[0][3], dp[1][2]) + 1 = min(3, 3) + 1 = 4.

3. Process "e" (row 2) vs "e", "a", "t":

   • 'e' == 'e': Match! Take diagonal dp[1][0] = 1.
   • 'e' != 'a': min(dp[1][2], dp[2][1]) + 1 = min(3, 1) + 1 = 2.
   • 'e' != 't': min(dp[1][3], dp[2][2]) + 1 = min(4, 2) + 1 = 3.

4. Process "a" (row 3) vs "e", "a", "t":

   • 'a' != 'e': min(dp[2][1], dp[3][0]) + 1 = min(1, 3) + 1 = 2.
   • 'a' == 'a': Match! Take diagonal dp[2][2] = 2.
   • 'a' != 't': min(dp[2][3], dp[3][2]) + 1 = min(3, 2) + 1 = 3.

5. Final Result: dp[3][3] is 2. (Delete 's' from "sea", delete 't' from "eat" -> "ea" == "ea").

Proof of Correctness

The correctness is proven via induction.

• Base Case: For strings of length 0, the number of deletions is simply the length of the non-empty string. Our initialization handles this correctly.
• Inductive Step: Assume dp correctly stores the minimum deletions for all prefix pairs smaller than (i, j).
  • If characters match, the optimal solution must extend the optimal solution for (i-1, j-1) because keeping matching characters never increases deletion cost.
  • If characters differ, one must be deleted. Since we explore both deleting word1[i] (relying on dp[i-1][j]) and deleting word2[j] (relying on dp[i][j-1]) and take the minimum, we guarantee local optimality.
• By the principle of optimality in Dynamic Programming, these local optimums lead to the global minimum for the full strings.

Pattern Reuse Notes

The DP - 2D Array pattern used here is highly transferable.

• LeetCode 72: Edit Distance: This is the generalized version of LeetCode 583. It allows insertion and replacement in addition to deletion. The logic is identical, just with two additional transition cases in the else block.
• LeetCode 712: Minimum ASCII Delete Sum for Two Strings: Instead of counting the number of steps (constant cost of 1), you sum the ASCII values of deleted characters. The structure is identical; only the cost addition changes (e.g., + word1[i-1] instead of + 1).

Reference Implementation

C++ Solution for LeetCode 583

1class Solution {
2public:
3    int minDistance(string word1, string word2) {
4        int m = word1.length();
5        int n = word2.length();
6        
7        // dp[i][j] stores the min steps to make word1[0..i-1] and word2[0..j-1] equal
8        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
9        
10        // Base cases: if one string is empty, we must delete all chars of the other
11        for (int i = 0; i <= m; i++) dp[i][0] = i;
12        for (int j = 0; j <= n; j++) dp[0][j] = j;
13        
14        for (int i = 1; i <= m; i++) {
15            for (int j = 1; j <= n; j++) {
16                if (word1[i - 1] == word2[j - 1]) {
17                    // Characters match, no new deletion needed
18                    dp[i][j] = dp[i - 1][j - 1];
19                } else {
20                    // Characters differ, delete from word1 or word2
21                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
22                }
23            }
24        }
25        
26        return dp[m][n];
27    }
28};

Java Solution for LeetCode 583

1class Solution {
2    public int minDistance(String word1, String word2) {
3        int m = word1.length();
4        int n = word2.length();
5        
6        // dp[i][j] represents min deletions for word1[0...i-1] and word2[0...j-1]
7        int[][] dp = new int[m + 1][n + 1];
8        
9        // Initialize first column
10        for (int i = 0; i <= m; i++) {
11            dp[i][0] = i;
12        }
13        
14        // Initialize first row
15        for (int j = 0; j <= n; j++) {
16            dp[0][j] = j;
17        }
18        
19        for (int i = 1; i <= m; i++) {
20            for (int j = 1; j <= n; j++) {
21                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
22                    // Characters match
23                    dp[i][j] = dp[i - 1][j - 1];
24                } else {
25                    // Characters mismatch: delete from word1 or word2
26                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
27                }
28            }
29        }
30        
31        return dp[m][n];
32    }
33}

Python Solution for LeetCode 583

1class Solution:
2    def minDistance(self, word1: str, word2: str) -> int:
3        m, n = len(word1), len(word2)
4        
5        # dp[i][j] stores min steps for word1[:i] and word2[:j]
6        dp = [[0] * (n + 1) for _ in range(m + 1)]
7        
8        # Base cases
9        for i in range(m + 1):
10            dp[i][0] = i
11        for j in range(n + 1):
12            dp[0][j] = j
13            
14        for i in range(1, m + 1):
15            for j in range(1, n + 1):
16                if word1[i - 1] == word2[j - 1]:
17                    # Match found, inherit result from diagonal
18                    dp[i][j] = dp[i - 1][j - 1]
19                else:
20                    # Mismatch, delete from word1 or word2
21                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
22                    
23        return dp[m][n]