Delete Operation for Two Strings

Med

#0558Time: 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.1 company

Patterns

Dynamic Programming

Data structures

String

Companies

ByteDance

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Algorithm

Define a recursive function calculate(s1, s2, i, j) that computes the minimum deletions for substrings s1[i:] and s2[j:].
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.
Base Case 2: Similarly, if j reaches the end of s2, return s1.length() - i.
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).
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.
The initial call is calculate(word1, word2, 0, 0).

Walkthrough

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

1public class Solution {2    public int minDistance(String word1, String word2) {3        return calculate(word1, word2, 0, 0);4    }5 6    private int calculate(String s1, String s2, int i, int j) {7        if (i == s1.length()) {8            return s2.length() - j;9        }10        if (j == s2.length()) {11            return s1.length() - i;12        }13 14        if (s1.charAt(i) == s2.charAt(j)) {15            return calculate(s1, s2, i + 1, j + 1);16        } else {17            return 1 + Math.min(calculate(s1, s2, i + 1, j), calculate(s1, s2, i, j + 1));18        }19    }20}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Use the same recursive structure as the brute-force approach.
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).
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.
If not, perform the recursive calculation as in the brute-force method.
Before returning the result, store it in memo[i][j] to avoid re-computation.

Walkthrough

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.

1public class Solution {2    public int minDistance(String word1, String word2) {3        Integer[][] memo = new Integer[word1.length()][word2.length()];4        return calculate(word1, word2, 0, 0, memo);5    }6 7    private int calculate(String s1, String s2, int i, int j, Integer[][] memo) {8        if (i == s1.length()) {9            return s2.length() - j;10        }11        if (j == s2.length()) {12            return s1.length() - i;13        }14        if (memo[i][j] != null) {15            return memo[i][j];16        }17 18        int result;19        if (s1.charAt(i) == s2.charAt(j)) {20            result = calculate(s1, s2, i + 1, j + 1, memo);21        } else {22            int deleteFromS1 = calculate(s1, s2, i + 1, j, memo);23            int deleteFromS2 = calculate(s1, s2, i, j + 1, memo);24            result = 1 + Math.min(deleteFromS1, deleteFromS2);25        }26        memo[i][j] = result;27        return result;28    }29}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Let m and n be the lengths of word1 and word2.
Create a 2D array dp of size (m+1) x (n+1).
dp[i][j] will store the minimum deletions to make word1[0...i-1] and word2[0...j-1] equal.
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).
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]).
The final answer is dp[m][n].

Walkthrough

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

1public class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length();4        int n = word2.length();5        int[][] dp = new int[m + 1][n + 1];6 7        for (int i = 0; i <= m; i++) {8            for (int j = 0; j <= n; j++) {9                if (i == 0) {10                    dp[i][j] = j; // Cost of deleting all j chars from word211                } else if (j == 0) {12                    dp[i][j] = i; // Cost of deleting all i chars from word113                } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {14                    dp[i][j] = dp[i - 1][j - 1];15                } else {16                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);17                }18            }19        }20        return dp[m][n];21    }22}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Let m and n be the lengths of word1 and word2. To optimize space, ensure n is the length of the shorter string.
Create a 1D array dp of size n+1.
Initialize dp to represent the base case (row 0 of the 2D table): dp[j] = j for j from 0 to n.
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.
Return dp[n].

Walkthrough

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.

1public class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length();4        int n = word2.length();5 6        // Ensure n is the smaller length for space optimization7        if (m < n) {8            return minDistance(word2, word1);9        }10 11        int[] dp = new int[n + 1];12        for (int j = 0; j <= n; j++) {13            dp[j] = j;14        }15 16        for (int i = 1; i <= m; i++) {17            int prev = dp[0]; // This will be dp[i-1][j-1] for the first j18            dp[0] = i; // This is dp[i][0]19            for (int j = 1; j <= n; j++) {20                int temp = dp[j]; // This is dp[i-1][j]21                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {22                    dp[j] = prev;23                } else {24                    // dp[j] is dp[i-1][j], dp[j-1] is dp[i][j-1]25                    dp[j] = 1 + Math.min(dp[j], dp[j - 1]);26                }27                prev = temp; // Update prev for the next iteration of j28            }29        }30        return dp[n];31    }32}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minDistance(String word1, String word2) {4    int m = word1.length(), n = word2.length();5    int[][] dp = new int[m + 1][n + 1];6    for (int i = 1; i <= m; ++i) {7      dp[i][0] = i;8    }9    for (int j = 1; j <= n; ++j) {10      dp[0][j] = j;11    }12    for (int i = 1; i <= m; ++i) {13      for (int j = 1; j <= n; ++j) {14        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {15          dp[i][j] = dp[i - 1][j - 1];16        } else {17          dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);18        }19      }20    }21    return dp[m][n];22  }23}

1class Solution {2public:3  int minDistance(string word1, string word2) {4    int m = word1.size(), n = word2.size();5    vector<vector<int>> dp(m + 1, vector<int>(n + 1));6    for (int i = 1; i <= m; ++i)7      dp[i][0] = i;8    for (int j = 1; j <= n; ++j)9      dp[0][j] = j;10    for (int i = 1; i <= m; ++i) {11      for (int j = 1; j <= n; ++j) {12        if (word1[i - 1] == word2[j - 1])13          dp[i][j] = dp[i - 1][j - 1];14        else15          dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);16      }17    }18    return dp[m][n];19  }20};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int minDistance(String word1, String word2) {4    int m = word1.length(), n = word2.length();5    int[][] dp = new int[m + 1][n + 1];6    for (int i = 1; i <= m; ++i) {7      dp[i][0] = i;8    }9    for (int j = 1; j <= n; ++j) {10      dp[0][j] = j;11    }12    for (int i = 1; i <= m; ++i) {13      for (int j = 1; j <= n; ++j) {14        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {15          dp[i][j] = dp[i - 1][j - 1];16        } else {17          dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);18        }19      }20    }21    return dp[m][n];22  }23}

1class Solution {2public:3  int minDistance(string word1, string word2) {4    int m = word1.size(), n = word2.size();5    vector<vector<int>> dp(m + 1, vector<int>(n + 1));6    for (int i = 1; i <= m; ++i)7      dp[i][0] = i;8    for (int j = 1; j <= n; ++j)9      dp[0][j] = j;10    for (int i = 1; i <= m; ++i) {11      for (int j = 1; j <= n; ++j) {12        if (word1[i - 1] == word2[j - 1])13          dp[i][j] = dp[i - 1][j - 1];14        else15          dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);16      }17    }18    return dp[m][n];19  }20};

1class Solution:2    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]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.