Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Delete Operation for Two Strings

MEDIUMProblemSolveExternal Links

Description

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.

The goal is to find the fewest total deletions (from both strings combined) so that both strings become identical. The characters you keep must appear in the same relative order as they did in the original strings — that is, the remaining characters form a common subsequence of both strings.

Examples

Example 1

Input: word1 = "sea", word2 = "eat"

Output: 2

Explanation: We need one deletion from "sea" to get "ea" (delete 's'), and one deletion from "eat" to get "ea" (delete 't'). After these 2 deletions, both strings become "ea". This is the minimum possible — the longest common subsequence of "sea" and "eat" is "ea" (length 2), so we delete 3 - 2 = 1 character from word1 and 3 - 2 = 1 character from word2, totaling 2 deletions.

Example 2

Input: word1 = "leetcode", word2 = "etco"

Output: 4

Explanation: The longest common subsequence of "leetcode" and "etco" is "etco" (length 4). We need to delete 8 - 4 = 4 characters from word1 ('l', 'e', 'd', 'e') and 4 - 4 = 0 characters from word2. Total deletions = 4.

Example 3

Input: word1 = "abc", word2 = "def"

Output: 6

Explanation: The two strings share no common characters at all. The longest common subsequence has length 0. We must delete all 3 characters from word1 and all 3 characters from word2 to make both empty strings (which are equal). Total deletions = 3 + 3 = 6.

Constraints

  • 1 ≤ word1.length, word2.length ≤ 500
  • word1 and word2 consist of only lowercase English letters.

Editorial

Brute Force

Intuition

The key insight connecting this problem to subsequences is: after we finish deleting characters from both strings, the remaining characters in each string must be identical. Since deletions preserve relative order, the remaining characters form a common subsequence of both strings.

To minimize total deletions, we want to maximize the number of characters we keep. The more characters we keep, the fewer we delete. The maximum characters we can keep is exactly the Longest Common Subsequence (LCS) of the two strings.

Once we know the LCS length, the answer is straightforward:

  • Characters deleted from word1 = len(word1) - LCS length
  • Characters deleted from word2 = len(word2) - LCS length
  • Total deletions = len(word1) + len(word2) - 2 × LCS length

The brute force approach finds the LCS using pure recursion. We compare characters from the end of both strings: if they match, they belong to the LCS; if not, we try skipping a character from one string or the other and take the better result.

Step-by-Step Explanation

Let's trace through with word1 = "sea" (m=3), word2 = "eat" (n=3):

We recursively compute LCS("sea", "eat").

Step 1: Compare last characters: s[2]='a' vs t[2]='t'. 'a' ≠ 't'. No match. Branch into two recursive calls: LCS("se", "eat") and LCS("sea", "ea").

Step 2: Branch A: LCS("se", "eat"). Compare s[1]='e' and t[2]='t'. 'e' ≠ 't'. Branch into LCS("s", "eat") and LCS("se", "ea").

Step 3: Branch A2: LCS("se", "ea"). Compare s[1]='e' and t[1]='a'. 'e' ≠ 'a'. Branch into LCS("s", "ea") and LCS("se", "e").

Step 4: Branch A2b: LCS("se", "e"). Compare s[1]='e' and t[0]='e'. Match! Result = 1 + LCS("s", "") = 1 + 0 = 1.

Step 5: Branch A2a: LCS("s", "ea"). Compare s[0]='s' and t[1]='a'. 's' ≠ 'a'. Branch into LCS("", "ea")=0 and LCS("s", "e").

Step 6: LCS("s", "e"): 's' ≠ 'e'. Branch into LCS("", "e")=0 and LCS("s", "")=0. Result = max(0,0) = 0.

Step 7: Back at LCS("s", "ea"): max(0, 0) = 0.

Step 8: Back at LCS("se", "ea"): max(0, 1) = 1.

Step 9: Branch B: LCS("sea", "ea"). Compare s[2]='a' and t[1]='a'. Match! Result = 1 + LCS("se", "e") = 1 + 1 = 2.

Step 10: LCS("se", "e"): s[1]='e' == t[0]='e'. Match! 1 + LCS("s", "") = 1 + 0 = 1. (Already computed in Step 4.)

Step 11: So LCS("sea", "ea") = 1 + 1 = 2.

Step 12: Root: max(Branch A result, Branch B result). After fully resolving Branch A we get LCS("se", "eat") = 1. So root = max(1, 2) = 2.

Step 13: LCS length = 2. Minimum deletions = 3 + 3 - 2×2 = 2.

Result: 2 deletions.

Recursive LCS Exploration for "sea" and "eat" — Watch how the recursion explores all possible ways to match characters between the two strings, branching at each mismatch and combining results at each match.

Algorithm

  1. Define a recursive function lcs(word1, word2, m, n) that returns the length of the LCS of word1[0..m-1] and word2[0..n-1].
  2. Base case: If m == 0 or n == 0, return 0 (one string is empty → no common subsequence).
  3. If word1[m-1] == word2[n-1]: Characters match. Return 1 + lcs(word1, word2, m-1, n-1).
  4. Else: Characters don't match. Return max(lcs(word1, word2, m-1, n), lcs(word1, word2, m, n-1)).
  5. Compute lcs_len = lcs(word1, word2, len(word1), len(word2)).
  6. Return len(word1) + len(word2) - 2 * lcs_len.

Code

class Solution {
public:
    int lcs(string& w1, string& w2, int m, int n) {
        if (m == 0 || n == 0) return 0;
        
        if (w1[m - 1] == w2[n - 1])
            return 1 + lcs(w1, w2, m - 1, n - 1);
        
        return max(lcs(w1, w2, m - 1, n), lcs(w1, w2, m, n - 1));
    }
    
    int minDistance(string word1, string word2) {
        int lcsLen = lcs(word1, word2, word1.size(), word2.size());
        return word1.size() + word2.size() - 2 * lcsLen;
    }
};
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def lcs(m: int, n: int) -> int:
            if m == 0 or n == 0:
                return 0
            
            if word1[m - 1] == word2[n - 1]:
                return 1 + lcs(m - 1, n - 1)
            
            return max(lcs(m - 1, n), lcs(m, n - 1))
        
        lcs_len = lcs(len(word1), len(word2))
        return len(word1) + len(word2) - 2 * lcs_len
class Solution {
    public int minDistance(String word1, String word2) {
        int lcsLen = lcs(word1, word2, word1.length(), word2.length());
        return word1.length() + word2.length() - 2 * lcsLen;
    }
    
    private int lcs(String w1, String w2, int m, int n) {
        if (m == 0 || n == 0) return 0;
        
        if (w1.charAt(m - 1) == w2.charAt(n - 1))
            return 1 + lcs(w1, w2, m - 1, n - 1);
        
        return Math.max(lcs(w1, w2, m - 1, n), lcs(w1, w2, m, n - 1));
    }
}

Complexity Analysis

Time Complexity: O(2^(m+n))

In the worst case (when no characters match), each call branches into two recursive calls. The recursion tree can have exponential depth. For strings of length m and n, the number of subproblems explored without memoization grows exponentially.

Space Complexity: O(m + n)

The recursion stack depth is bounded by m + n in the worst case (reducing one index per call). No additional data structures are used.

Why This Approach Is Not Efficient

The exponential time complexity O(2^(m+n)) makes this approach completely impractical for the given constraints (strings up to length 500). Even for modest inputs like m = n = 20, the recursion would explore over a million calls.

The core problem is overlapping subproblems. The same (m, n) pair gets computed many times through different recursive paths. For example, lcs(2, 2) might be reached from lcs(3, 2) → lcs(2, 2) and also from lcs(2, 3) → lcs(2, 2). This redundancy compounds exponentially.

Since there are only O(m × n) unique subproblems, caching results with memoization eliminates all redundant computation, bringing the time down to O(m × n).

Better Approach - Memoization (Top-Down DP)

Intuition

The recursive solution recomputes the same subproblems repeatedly. We can fix this by storing each result in a 2D table so that every (m, n) pair is computed only once.

Think of it like filling out a worksheet. The first time you solve a sub-question, you write down the answer. Every time that same sub-question comes up again, you just look at your worksheet instead of reworking it from scratch.

The recursion structure remains identical — we simply add a lookup before each computation and save the result after. This single change transforms the exponential algorithm into a polynomial one.

Step-by-Step Explanation

Let's trace with word1 = "sea" (m=3), word2 = "eat" (n=3) using memoization:

Step 1: Initialize a 4×4 memo table (indices 0..3 for each) with all values -1.

Step 2: Call lcs(3,3). Not in memo. word1[2]='a' ≠ word2[2]='t'. Branch to lcs(2,3) and lcs(3,2).

Step 3: Call lcs(2,3). Not in memo. word1[1]='e' ≠ word2[2]='t'. Branch to lcs(1,3) and lcs(2,2).

Step 4: Call lcs(2,2). Not in memo. word1[1]='e' ≠ word2[1]='a'. Branch to lcs(1,2) and lcs(2,1).

Step 5: Call lcs(2,1). Not in memo. word1[1]='e' == word2[0]='e'. Match! lcs(2,1) = 1 + lcs(1,0) = 1 + 0 = 1. Store memo[2][1] = 1.

Step 6: Call lcs(1,2). Not in memo. word1[0]='s' ≠ word2[1]='a'. Branch to lcs(0,2)=0 and lcs(1,1). lcs(1,1): word1[0]='s' ≠ word2[0]='e' → max(lcs(0,1), lcs(1,0)) = 0. Store memo[1][1] = 0. lcs(1,2) = max(0, 0) = 0. Store memo[1][2] = 0.

Step 7: Back at lcs(2,2): max(memo[1][2], memo[2][1]) = max(0, 1) = 1. Store memo[2][2] = 1.

Step 8: Call lcs(1,3). Not in memo. word1[0]='s' ≠ word2[2]='t'. Branches resolve to 0. Store memo[1][3] = 0.

Step 9: Back at lcs(2,3): max(memo[1][3], memo[2][2]) = max(0, 1) = 1. Store memo[2][3] = 1.

Step 10: Call lcs(3,2). Not in memo. word1[2]='a' == word2[1]='a'. Match! lcs(3,2) = 1 + lcs(2,1). Memo lookup: memo[2][1] = 1 (already computed!). lcs(3,2) = 1 + 1 = 2. Store memo[3][2] = 2.

Step 11: Back at root lcs(3,3): max(memo[2][3], memo[3][2]) = max(1, 2) = 2. Store memo[3][3] = 2.

Step 12: LCS = 2. Answer = 3 + 3 - 2×2 = 2.

Result: 2 deletions. Notice in Step 10, memo[2][1] was reused — memoization prevented recomputation.

Algorithm

  1. Create an (m+1)×(n+1) memo table initialized to -1.
  2. Define recursive function lcs(w1, w2, m, n, memo):
    • If m == 0 or n == 0, return 0.
    • If memo[m][n] != -1, return the cached value.
    • If w1[m-1] == w2[n-1]: memo[m][n] = 1 + lcs(w1, w2, m-1, n-1, memo).
    • Else: memo[m][n] = max(lcs(w1, w2, m-1, n, memo), lcs(w1, w2, m, n-1, memo)).
    • Return memo[m][n].
  3. Compute lcs_len = lcs(w1, w2, len(w1), len(w2), memo).
  4. Return len(w1) + len(w2) - 2 * lcs_len.

Code

class Solution {
public:
    int lcs(string& w1, string& w2, int m, int n, vector<vector<int>>& memo) {
        if (m == 0 || n == 0) return 0;
        if (memo[m][n] != -1) return memo[m][n];
        
        if (w1[m - 1] == w2[n - 1])
            return memo[m][n] = 1 + lcs(w1, w2, m - 1, n - 1, memo);
        
        return memo[m][n] = max(lcs(w1, w2, m - 1, n, memo), lcs(w1, w2, m, n - 1, memo));
    }
    
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
        int lcsLen = lcs(word1, word2, m, n, memo);
        return m + n - 2 * lcsLen;
    }
};
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        memo = [[-1] * (n + 1) for _ in range(m + 1)]
        
        def lcs(i: int, j: int) -> int:
            if i == 0 or j == 0:
                return 0
            if memo[i][j] != -1:
                return memo[i][j]
            
            if word1[i - 1] == word2[j - 1]:
                memo[i][j] = 1 + lcs(i - 1, j - 1)
            else:
                memo[i][j] = max(lcs(i - 1, j), lcs(i, j - 1))
            
            return memo[i][j]
        
        lcs_len = lcs(m, n)
        return m + n - 2 * lcs_len
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] memo = new int[m + 1][n + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        int lcsLen = lcs(word1, word2, m, n, memo);
        return m + n - 2 * lcsLen;
    }
    
    private int lcs(String w1, String w2, int m, int n, int[][] memo) {
        if (m == 0 || n == 0) return 0;
        if (memo[m][n] != -1) return memo[m][n];
        
        if (w1.charAt(m - 1) == w2.charAt(n - 1))
            memo[m][n] = 1 + lcs(w1, w2, m - 1, n - 1, memo);
        else
            memo[m][n] = Math.max(lcs(w1, w2, m - 1, n, memo), lcs(w1, w2, m, n - 1, memo));
        
        return memo[m][n];
    }
}

Complexity Analysis

Time Complexity: O(m × n)

There are (m+1) × (n+1) unique subproblems. Each is computed exactly once and cached. Each computation does O(1) work (one comparison and at most two lookups). Total: O(m × n).

Space Complexity: O(m × n)

The memoization table stores (m+1) × (n+1) values. The recursion stack can go up to O(m + n) deep. The dominant cost is the m × n memo table.

Why This Approach Is Not Efficient

Memoization reduces time to O(m × n), which is efficient enough for the constraints. However, it still uses O(m × n) space for the memo table, plus additional O(m + n) space for the recursion call stack. For m = n = 500, this means 250,000 table entries plus potential deep recursion.

The recursion also carries overhead: function call costs, stack frame allocation, and the risk of stack overflow for very deep recursion chains. We can eliminate all recursive overhead by converting to a bottom-up iterative approach (tabulation), and further optimize space by observing that each row of the DP table only depends on the previous row — reducing space from O(m × n) to O(min(m, n)).

Optimal Approach - Bottom-Up DP with Space Optimization

Intuition

Instead of recursing from the end and caching, we build the LCS table iteratively from the ground up. We define dp[i][j] as the LCS length of word1[0..i-1] and word2[0..j-1].

The recurrence is:

  • If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (both characters extend the LCS)
  • Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip whichever character gives a longer LCS)

The space optimization exploits a key dependency pattern: when filling row i, we only look at row i-1 (the previous row). We never look further back. So instead of storing the entire m×n table, we can use just two arrays of size n+1: one for the current row and one for the previous row.

The final answer remains: m + n - 2 * dp[m][n].

Step-by-Step Explanation

Let's trace with word1 = "sea" (m=3), word2 = "eat" (n=3):

We build a (m+1)×(n+1) DP table where rows represent characters of word1 and columns represent characters of word2.

Step 1: Initialize first row and first column to 0 (LCS of any string with an empty string is 0).

Step 2: dp[1][1]: word1[0]='s', word2[0]='e'. 's' ≠ 'e'. dp[1][1] = max(dp[0][1], dp[1][0]) = max(0, 0) = 0.

Step 3: dp[1][2]: word1[0]='s', word2[1]='a'. 's' ≠ 'a'. dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 0) = 0.

Step 4: dp[1][3]: word1[0]='s', word2[2]='t'. 's' ≠ 't'. dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 0) = 0.

Step 5: dp[2][1]: word1[1]='e', word2[0]='e'. Match! dp[2][1] = dp[1][0] + 1 = 0 + 1 = 1.

Step 6: dp[2][2]: word1[1]='e', word2[1]='a'. 'e' ≠ 'a'. dp[2][2] = max(dp[1][2], dp[2][1]) = max(0, 1) = 1.

Step 7: dp[2][3]: word1[1]='e', word2[2]='t'. 'e' ≠ 't'. dp[2][3] = max(dp[1][3], dp[2][2]) = max(0, 1) = 1.

Step 8: dp[3][1]: word1[2]='a', word2[0]='e'. 'a' ≠ 'e'. dp[3][1] = max(dp[2][1], dp[3][0]) = max(1, 0) = 1.

Step 9: dp[3][2]: word1[2]='a', word2[1]='a'. Match! dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2.

Step 10: dp[3][3]: word1[2]='a', word2[2]='t'. 'a' ≠ 't'. dp[3][3] = max(dp[2][3], dp[3][2]) = max(1, 2) = 2.

Step 11: LCS length = dp[3][3] = 2. Minimum deletions = 3 + 3 - 2×2 = 2.

Result: 2 deletions.

LCS DP Table Fill for "sea" vs "eat" — Watch how we build the LCS table row by row, comparing each character pair and either extending the LCS on a match or taking the best from adjacent cells on a mismatch.

Algorithm

  1. Let m = len(word1), n = len(word2).
  2. Create two arrays prev and curr of size n + 1, initialized to 0.
  3. For each i from 1 to m:
    a. Reset curr[0] = 0.
    b. For each j from 1 to n:
    • If word1[i-1] == word2[j-1]: curr[j] = prev[j-1] + 1
    • Else: curr[j] = max(prev[j], curr[j-1])
      c. Copy curr into prev.
  4. The LCS length is prev[n].
  5. Return m + n - 2 * prev[n].

Code

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<int> prev(n + 1, 0), curr(n + 1, 0);
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = max(prev[j], curr[j - 1]);
                }
            }
            prev = curr;
            fill(curr.begin(), curr.end(), 0);
        }
        
        return m + n - 2 * prev[n];
    }
};
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        prev = [0] * (n + 1)
        curr = [0] * (n + 1)
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = curr[:]
            curr = [0] * (n + 1)
        
        return m + n - 2 * prev[n]
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            System.arraycopy(curr, 0, prev, 0, n + 1);
            Arrays.fill(curr, 0);
        }
        
        return m + n - 2 * prev[n];
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We have two nested loops: the outer runs m times and the inner runs n times. Each cell computation is O(1) — a character comparison and a constant number of array lookups. For the maximum constraints (m = n = 500), this is 250,000 operations — very fast.

Space Complexity: O(n)

Instead of storing the full (m+1) × (n+1) DP table, we use only two arrays of size n+1 (prev and curr). At each row, the current cell only depends on values from the current row (left neighbor) and the previous row (directly above and diagonal). This optimization reduces space from O(m × n) to O(n). For n = 500, this means just 1,000 integers instead of 250,000.