Delete Operation for Two Strings

Medium
318.

Delete Operation for Two Strings

Delete Operation for Two Strings is a medium coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Given two strings word1 and word2, return the minimum number of single-character deletions needed to make them equal. A deletion may be applied to either string.

Example 1

Input
word1 = "sea", word2 = "eat"
Output
2
Explanation
Delete "s" from the first and "t" from the second, leaving "ea".

Example 2

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

Example 3

Input
word1 = "abc", word2 = "abc"
Output
0

Constraints

  • 1 <= word1.length, word2.length <= 25
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Operation for Two Strings — Problem & Solution

Delete Operation for Two Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Delete Operation for Two Strings is a medium coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given two strings word1 and word2, return the minimum number of single-character deletions needed to make them equal. A deletion may be applied to either string.

Example 1

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: Delete "s" from the first and "t" from the second, leaving "ea".

Example 2

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

Example 3

Input: word1 = "abc", word2 = "abc"
Output: 0

Constraints

  • 1 <= word1.length, word2.length <= 25
  • Both consist of lowercase English letters.

Hints for Delete Operation for Two Strings

  1. Hint 1

    Whatever survives the deletions is a common subsequence of both strings.

  2. Hint 2

    To delete as little as possible, keep the longest common subsequence.

  3. Hint 3

    The answer is then len(a) + len(b) - 2 × LCS.

How to solve Delete Operation for Two Strings

What survives the deletions is a common subsequence; keeping the longest one minimises deletions, so the answer is m + n - 2·LCS.

Approach

  1. Compute the LCS table: equal characters take the diagonal + 1, otherwise the max of up and left.
  2. Return m + n - 2 · dp[m][n].

Why it works

Every character not in the kept common subsequence must be deleted from its own string; the kept part is longest when it is the LCS.

Complexity

  • Time — O(m · n)
  • Space — O(m · n), reducible to one row

Pitfalls

  • This is edit distance with only deletions — do not add the substitution transition.

Reference solution

Python

def minDistance(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):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return m + n - 2 * dp[m][n]

Java

public static 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++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return m + n - 2 * dp[m][n];
}

C++

int minDistance(string word1, string word2) {
    int m = (int) word1.size(), n = (int) word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    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] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return m + n - 2 * dp[m][n];
}

JavaScript

var minDistance = function(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = [];
    for (let i = 0; i <= m; i++) dp.push(new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return m + n - 2 * dp[m][n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming