# Delete Operation for Two Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-operation-for-two-strings)
Canonical: https://scaleengineer.com/dsa/problems/delete-operation-for-two-strings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance)
---
## Problem
Given two strings `word1` and `word2`, return _the minimum number of **steps** required to make_ `word1` _and_ `word2` _the same_.

In one **step**, you can delete exactly one character in either string.

**Example 1:**

**Input:** word1 = "sea", word2 = "eat"
**Output:** 2
**Explanation:** You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

**Example 2:**

**Input:** word1 = "leetcode", word2 = "etco"
**Output:** 4

**Constraints:**

* `1 <= word1.length, word2.length <= 500`
* `word1` and `word2` consist of only lowercase English letters.

# Approaches
## Brute-Force Recursion
This approach uses a straightforward recursive function to solve the problem. The function explores all possible sequences of deletions from both strings to make them equal. It directly computes the minimum number of deletions by making local optimal choices at each step.
**Time:** O(2^(m+n)). For each mismatch, the function branches into two recursive calls, leading to an exponential number of computations. · **Space:** O(m + n), where m and n are the lengths of the two strings. This space is used by the recursion call stack.
**Pros:** Simple to understand and implement the recursive logic.; Directly translates the problem definition into code.
**Cons:** Extremely inefficient due to exponential time complexity.; Results in 'Time Limit Exceeded' for all but the smallest inputs because it recomputes the same subproblems repeatedly.
### Explanation
We define a recursive function, say `calculate(s1, s2, i, j)`, which computes the minimum deletions needed for the substrings `s1` starting from index `i` and `s2` starting from index `j`.

- **Base Cases:**
  - If we have reached the end of `s1` (i.e., `i == s1.length()`), we must delete all remaining characters in `s2`. The cost is `s2.length() - j`.
  - Similarly, if `j == s2.length()`, the cost is `s1.length() - i`.

- **Recursive Step:**
  - If the characters `s1.charAt(i)` and `s2.charAt(j)` are the same, they form part of the common string. We don't need to delete them. We simply move to the next characters in both strings: `calculate(s1, s2, i + 1, j + 1)`.
  - If the characters are different, we have two choices:
    1. Delete the character `s1.charAt(i)` and find the minimum deletions for `s1[i+1:]` and `s2[j:]`. The cost is `1 + calculate(s1, s2, i + 1, j)`.
    2. Delete the character `s2.charAt(j)` and find the minimum deletions for `s1[i:]` and `s2[j+1:]`. The cost is `1 + calculate(s1, s2, i, j + 1)`.
  - We take the minimum of these two choices.

The initial call to the function would be `calculate(word1, word2, 0, 0)`.

```java
public class Solution {
    public int minDistance(String word1, String word2) {
        return calculate(word1, word2, 0, 0);
    }

    private int calculate(String s1, String s2, int i, int j) {
        if (i == s1.length()) {
            return s2.length() - j;
        }
        if (j == s2.length()) {
            return s1.length() - i;
        }

        if (s1.charAt(i) == s2.charAt(j)) {
            return calculate(s1, s2, i + 1, j + 1);
        } else {
            return 1 + Math.min(calculate(s1, s2, i + 1, j), calculate(s1, s2, i, j + 1));
        }
    }
}
```
### Algorithm
1. Define a recursive function `calculate(s1, s2, i, j)` that computes the minimum deletions for substrings `s1[i:]` and `s2[j:]`.
2. **Base Case 1:** If `i` reaches the end of `s1`, it means `s1` is exhausted. To make the remaining part of `s2` (`s2[j:]`) empty, we must delete all its characters. Return `s2.length() - j`.
3. **Base Case 2:** Similarly, if `j` reaches the end of `s2`, return `s1.length() - i`.
4. **Recursive Step (Characters Match):** If `s1.charAt(i)` equals `s2.charAt(j)`, these characters can be part of the final common string. No deletion is needed for them. Recur for the rest of the strings: `calculate(s1, s2, i + 1, j + 1)`.
5. **Recursive Step (Characters Mismatch):** If `s1.charAt(i)` is not equal to `s2.charAt(j)`, we must delete at least one of them. We explore two possibilities:
    a. Delete `s1.charAt(i)`: The cost is `1 + calculate(s1, s2, i + 1, j)`.
    b. Delete `s2.charAt(j)`: The cost is `1 + calculate(s1, s2, i, j + 1)`.
    Return the minimum of these two possibilities.
6. The initial call is `calculate(word1, word2, 0, 0)`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. It stores the results of expensive function calls (subproblems) and returns the cached result when the same inputs occur again. This avoids redundant computations and drastically improves performance.
**Time:** O(m * n). Each of the `m*n` subproblems is solved exactly once. · **Space:** O(m * n) for the memoization table, plus O(m+n) for the recursion stack. The table size is the dominant factor.
**Pros:** Significantly more efficient than brute-force, with a polynomial time complexity.; Guaranteed to find the optimal solution.; Can pass the given constraints.
**Cons:** Uses O(m*n) space for the memoization table, which can be large.; May lead to a `StackOverflowError` for very deep recursion, although the problem constraints (lengths up to 500) are generally manageable.
### Explanation
The recursive logic remains identical to the brute-force approach, but we add a cache (a 2D array, `memo`) to store the results. The state of each subproblem is defined by the indices `(i, j)`.

- `memo[i][j]` will store the minimum deletions required for `word1[i:]` and `word2[j:]`.
- Before computing the result for `(i, j)`, we check if `memo[i][j]` already holds a valid answer. If it does, we return it directly.
- Otherwise, we compute the result using the same recursive formula and store it in `memo[i][j]` before returning.

This ensures that each subproblem `(i, j)` is solved only once.

```java
public class Solution {
    public int minDistance(String word1, String word2) {
        Integer[][] memo = new Integer[word1.length()][word2.length()];
        return calculate(word1, word2, 0, 0, memo);
    }

    private int calculate(String s1, String s2, int i, int j, Integer[][] memo) {
        if (i == s1.length()) {
            return s2.length() - j;
        }
        if (j == s2.length()) {
            return s1.length() - i;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int result;
        if (s1.charAt(i) == s2.charAt(j)) {
            result = calculate(s1, s2, i + 1, j + 1, memo);
        } else {
            int deleteFromS1 = calculate(s1, s2, i + 1, j, memo);
            int deleteFromS2 = calculate(s1, s2, i, j + 1, memo);
            result = 1 + Math.min(deleteFromS1, deleteFromS2);
        }
        memo[i][j] = result;
        return result;
    }
}
```
### Algorithm
1. Use the same recursive structure as the brute-force approach.
2. Create a 2D array `memo` of size `m x n` (where `m` and `n` are string lengths) to store the results of subproblems. Initialize it with a sentinel value (e.g., `null` or -1).
3. In the recursive function `calculate(s1, s2, i, j, memo)`, first check if `memo[i][j]` has been computed. If so, return the stored value.
4. If not, perform the recursive calculation as in the brute-force method.
5. Before returning the result, store it in `memo[i][j]` to avoid re-computation.

## 2D Dynamic Programming
This approach uses an iterative, bottom-up dynamic programming solution. It builds a 2D table `dp` where `dp[i][j]` stores the minimum number of deletions to make the prefix `word1[0...i-1]` and `word2[0...j-1]` identical. This avoids recursion and its associated overhead, often making it slightly faster in practice than the memoized version.
**Time:** O(m * n). We iterate through each cell of the `(m+1) x (n+1)` DP table once. · **Space:** O(m * n) for the 2D DP table.
**Pros:** Efficient and robust, with no risk of stack overflow.; Conceptually clear and a standard DP pattern.; Often slightly faster than memoization due to the absence of recursion overhead.
**Cons:** Requires O(m*n) space, which might be a concern for extremely large inputs, though it's acceptable for the given constraints.
### Explanation
This problem can be reframed as finding the Longest Common Subsequence (LCS). The total number of characters to delete is the sum of the lengths of the two strings minus twice the length of their LCS. The DP formulation below calculates the minimum deletions directly, which is equivalent.

We create a `dp` table of size `(m+1) x (n+1)`.

- **Initialization:**
  - `dp[0][0] = 0` (two empty strings need 0 deletions).
  - The first row `dp[0][j]` is initialized to `j`, as making an empty string and `word2[0...j-1]` equal requires `j` deletions.
  - The first column `dp[i][0]` is initialized to `i`, as making `word1[0...i-1]` and an empty string equal requires `i` deletions.

- **Iteration:**
  - We fill the table row by row, column by column.
  - For each cell `dp[i][j]`, we look at `word1.charAt(i-1)` and `word2.charAt(j-1)`.
  - If they match, no deletion is needed for these characters. The cost is inherited from the solution for the smaller prefixes: `dp[i][j] = dp[i-1][j-1]`.
  - If they don't match, we must perform a deletion. The optimal choice is the minimum of deleting from `word1` (cost `dp[i-1][j]`) or from `word2` (cost `dp[i][j-1]`), plus 1 for the current deletion: `dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1])`.

The final answer is the value in the bottom-right cell, `dp[m][n]`.

```java
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j; // Cost of deleting all j chars from word2
                } else if (j == 0) {
                    dp[i][j] = i; // Cost of deleting all i chars from word1
                } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
```
### Algorithm
1. Let `m` and `n` be the lengths of `word1` and `word2`.
2. Create a 2D array `dp` of size `(m+1) x (n+1)`.
3. `dp[i][j]` will store the minimum deletions to make `word1[0...i-1]` and `word2[0...j-1]` equal.
4. **Initialize Base Cases:**
   - `dp[i][0] = i` for `i` from 0 to `m`. (To make `word1` of length `i` equal to an empty string, delete `i` characters).
   - `dp[0][j] = j` for `j` from 0 to `n`. (To make an empty string equal to `word2` of length `j`, delete `j` characters).
5. **Fill the Table:** Iterate `i` from 1 to `m` and `j` from 1 to `n`:
   - If `word1.charAt(i-1) == word2.charAt(j-1)`: The last characters match, so no new deletion is needed. `dp[i][j] = dp[i-1][j-1]`.
   - Else: The characters differ. We must delete one. `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])`.
6. The final answer is `dp[m][n]`.

## 1D Space-Optimized Dynamic Programming
This is the most efficient approach in terms of space. It optimizes the 2D DP solution by observing that to compute the values for the current row of the DP table, we only need the values from the immediately preceding row. This allows us to reduce the space complexity from `O(m*n)` to `O(min(m, n))` by using only a single 1D array.
**Time:** O(m * n). The nested loop structure remains the same as the 2D DP approach. · **Space:** O(min(m, n)). We use a 1D array whose size is determined by the length of the shorter string.
**Pros:** Most space-efficient solution.; Maintains the optimal O(m*n) time complexity.
**Cons:** The logic is slightly more complex to reason about compared to the 2D DP approach.; Requires careful management of temporary variables to correctly simulate the dependencies from the 2D table.
### Explanation
We can optimize the space of the bottom-up DP approach. Notice that the calculation of `dp[i][j]` only depends on values from the current row (`dp[i][j-1]`) and the previous row (`dp[i-1][j]` and `dp[i-1][j-1]`). This suggests we don't need to store the entire 2D table.

A 1D array, `dp`, of size `n+1` is sufficient. This array will store the values of a single row of our conceptual 2D table. As we iterate through `word1` (outer loop for `i`), we will update this `dp` array to reflect the calculations for the `i`-th row.

The key challenge is that when we compute `dp[j]` (for the current row `i`), we need `dp[i-1][j-1]`. However, `dp[j-1]` in our 1D array has already been updated to be `dp[i][j-1]`. To solve this, we use a variable, `prev`, to save the value of `dp[i-1][j-1]` before it gets overwritten.

```java
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // Ensure n is the smaller length for space optimization
        if (m < n) {
            return minDistance(word2, word1);
        }

        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }

        for (int i = 1; i <= m; i++) {
            int prev = dp[0]; // This will be dp[i-1][j-1] for the first j
            dp[0] = i; // This is dp[i][0]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // This is dp[i-1][j]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;
                } else {
                    // dp[j] is dp[i-1][j], dp[j-1] is dp[i][j-1]
                    dp[j] = 1 + Math.min(dp[j], dp[j - 1]);
                }
                prev = temp; // Update prev for the next iteration of j
            }
        }
        return dp[n];
    }
}
```
### Algorithm
1. Let `m` and `n` be the lengths of `word1` and `word2`. To optimize space, ensure `n` is the length of the shorter string.
2. Create a 1D array `dp` of size `n+1`.
3. Initialize `dp` to represent the base case (row 0 of the 2D table): `dp[j] = j` for `j` from 0 to `n`.
4. Iterate `i` from 1 to `m` (for each row of the conceptual 2D table):
   a. Before the inner loop, store the value that will represent the diagonal element `dp[i-1][j-1]`. Let's call it `prev`. Initialize `prev = dp[0]` (which is `dp[i-1][0]`).
   b. Update `dp[0]` for the current row `i`: `dp[0] = i`.
   c. Iterate `j` from 1 to `n` (for each column):
      i. Store the current `dp[j]` (which corresponds to `dp[i-1][j]`) in a `temp` variable.
      ii. If `word1.charAt(i-1) == word2.charAt(j-1)`, update `dp[j] = prev`.
      iii. Else, update `dp[j] = 1 + min(dp[j], dp[j-1])`. Here, `dp[j]` is the value from the previous row and `dp[j-1]` is the already updated value from the current row.
      iv. Update `prev = temp` to prepare for the next `j`.
5. Return `dp[n]`.

# Solutions
### Java

```java
class Solution {
public
  int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      dp[i][0] = i;
    }
    for (int j = 1; j <= n; ++j) {
      dp[0][j] = j;
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    return dp[m][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i)
      dp[i][0] = i;
    for (int j = 1; j <= n; ++j)
      dp[0][j] = j;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (word1[i - 1] == word2[j - 1])
          dp[i][j] = dp[i - 1][j - 1];
        else
          dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
      }
    }
    return dp[m][n];
  }
};

```

### Python

```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): dp[i][0] = i for j in range(1, n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]) return dp[- 1][- 1]

```