Erase the Earliest Matching Block Repeatedly
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Starting with lowercase string `s`, repeatedly delete the leftmost occurrence of the nonempty string `part`. Search the updated string after each deletion and stop only when `part` no longer occurs. Return the final string; a deletion can create a new occurrence where its two sides meet.
```cpp
class Solution {
public:
string removeOccurrences(string s, string part);
};
```
### Examples
**Example 1:**
```text
s = "aabcbc", part = "abc"
Output: ""
Explanation: Removing the match starting at index 1 leaves "abc", which is removed next.
```
**Example 2:**
```text
s = "zzxyxyq", part = "xy"
Output: "zzq"
Explanation: The two leftmost matches are removed in sequence.
```
### Constraints
- `1 <= s.length, part.length <= 1000`.
- Both strings contain lowercase English letters.
### Clarifying Questions
The position search restarts on the changed string after every removal. Overlapping matches are resolved by the leftmost rule.
```hint Inspect the structure
Why can searching only the untouched suffix miss a newly created match?
```
### Reasoning checkpoints
- Match the specified leftmost deletion order, including overlaps and matches created after an earlier deletion.
- Explain why the process terminates and why the returned string contains no remaining match.
### Optional extensions
How could an implementation avoid repeatedly shifting the remaining characters after a deletion?
Overview: Erase the Earliest Matching Block Repeatedly. Given lowercase strings s and part, repeatedly remove the leftmost occurrence of part from the current string. Stop when no occurrence remains and return the resulting string. A deletion can create another match across the joined boundary.