Delete Operation for Two Strings
Medium · Dynamic Programming · String · Dynamic Programming
Problem
You are given two strings word1 and word2. In one step you delete exactly one character from either string.
Return the minimum number of steps needed to make the two strings identical. Two empty strings count as identical.
Examples
Input: word1 = "heart", word2 = "earth" Output: 2
Delete 'h' from the front of "heart" and 'h' from the end of "earth" to leave "eart" in both.
Input: word1 = "abc", word2 = "xyz" Output: 6
The strings share no letters, so both must be deleted entirely.
Input: word1 = "sea", word2 = "eat" Output: 2
Keep "ea": delete "s" from the first word and "t" from the second.
Constraints
- 1 <= word1.length, word2.length <= 500
- Both strings consist of lowercase English letters.
Approaches
- Baseline: deletions table — time O(m · n), space O(m · n)
Follow-up
With deletions only, the problem reduces to the longest common subsequence. The use cases change the rules: a goal where only the letters count and not their order, and deletions allowed from the first word only.
Related problems
Start free on Cariara · Coding problems · System design studio
