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.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 25Both consist of lowercase English letters.
Hints for Delete Operation for Two Strings
Hint 1
Whatever survives the deletions is a common subsequence of both strings.
Hint 2
To delete as little as possible, keep the longest common subsequence.
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
- Compute the LCS table: equal characters take the diagonal + 1, otherwise the max of up and left.
- 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