Minimize Single-Character Deletions to Equalize Two Words
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the fewest deletions needed to make word1 and word2 equal. One step deletes exactly one character from either word; insertions and replacements are not allowed.
```cpp
class Solution {
public:
int minDistance(string word1, string word2);
};
```
### Examples
**Example 1:**
```text
word1 = "park", word2 = "spark"
Output: 1
Explanation: Delete the initial s from the second word.
```
**Example 2:**
```text
word1 = "ab", word2 = "cd"
Output: 4
Explanation: Both words must become empty.
```
### Constraints
- Each input word has 1..500 English lowercase characters.
### Clarifying Questions
Use only deletions and connect their minimum number to the longest preserved common subsequence.
```hint Read the boundary condition
What must the shared surviving string be a subsequence of?
```
### Contract considerations
Use only deletions and connect their minimum number to the longest preserved common subsequence.
Overview: Minimize Single-Character Deletions to Equalize Two Words. Return the fewest deletions needed to make word1 and word2 equal.