Watch 10 video solutions for Delete Operation for Two Strings, a medium level problem involving String, Dynamic Programming. This walkthrough by Algorithms Made Easy has 7,421 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 500word1 and word2 consist of only lowercase English letters.Problem Overview: Given two strings word1 and word2, return the minimum number of delete operations required to make both strings identical. You can delete characters from either string, but you cannot insert or replace.
Approach 1: Brute Force Recursion (Exponential Time)
Try every possible deletion choice recursively. If the current characters match, move both pointers forward. If they differ, branch into two possibilities: delete from word1 or delete from word2. Take the minimum result from both paths. This explores a full decision tree with repeated subproblems, leading to O(2^(m+n)) time and O(m+n) recursion stack space. Useful for understanding the state transition before introducing memoization or dynamic programming.
Approach 2: Dynamic Programming with Longest Common Subsequence (O(m*n))
The key insight: both strings become equal when only their Longest Common Subsequence (LCS) remains. Any character not part of the LCS must be deleted. If the LCS length is lcs, then the required deletions equal (m - lcs) + (n - lcs), where m and n are the lengths of the two strings.
Compute the LCS using classic Dynamic Programming. Build a (m+1) x (n+1) DP table where dp[i][j] stores the LCS length of the first i characters of word1 and first j characters of word2. If characters match, extend the subsequence using dp[i-1][j-1] + 1. Otherwise take max(dp[i-1][j], dp[i][j-1]). This runs in O(m*n) time with O(m*n) space.
The approach works because deleting characters until both strings equal the LCS ensures the minimum number of operations. The DP transition mirrors the classic String comparison pattern used in the Dynamic Programming formulation of Longest Common Subsequence.
Recommended for interviews: Dynamic Programming using the Longest Common Subsequence. Interviewers expect candidates to recognize that the minimum deletions problem reduces directly to LCS. Starting with the brute-force recursion shows you understand the decision process, but deriving the LCS relationship and implementing the O(m*n) DP demonstrates strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^(m+n)) | O(m+n) | Conceptual understanding of the decision tree before optimization |
| Dynamic Programming with LCS | O(m*n) | O(m*n) | General optimal solution for interview and production use |
| Space Optimized LCS DP | O(m*n) | O(min(m,n)) | When memory usage matters for very long strings |