What is Bomb String Removal?
This problem asks you to repeatedly remove a fixed 'bomb pattern' wherever it appears consecutively in a string. When a part is removed, the sides merge and may form a new pattern, so you keep removing until none remain.
For example, in the jelly row "mirkAAkkx" with bomb pattern "kk", the middle kk pops and leaves "mirkAAx".
Why a Stack?
The naive approach is "find the pattern, erase it, restart from the beginning." But this rescans the whole string after every removal, ballooning to O(n²) or worse.
Key insight: an explosion always happens at the tail of what you just stacked. The earlier part is already settled; if a new character creates a new pattern, it must form at the very end.
That is why we use a stack. Push characters one by one, and the moment the top K characters equal the bomb pattern, pop those K at once. Chain reactions from merging sides are handled automatically — after popping, the characters beneath naturally become the new tail.
How It Works
Step 1. Push each character onto the stack, left to right.
Step 2. Right after pushing, check whether the pushed char equals the last char of the bomb. (If not, the pattern can never complete, so skip the comparison — a small optimization.)
Step 3. If it matches, compare the top K chars with the bomb pattern.
- •Match: pop the top K (pop!)
- •No match: leave them.
Step 4. After scanning everything, whatever remains on the stack is the answer. Print "EMPTY" if empty.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n) |
| Space | O(n) |
Each character is pushed at most once and popped at most once. We scan the string just once, so the total is O(n).
Common Mistakes
- •Rescanning from the start every time: scanning from index 0 after each removal is O(n²). Use a stack and look only at the tail.
- •Repeated string replace:
while (s.contains(bomb)) s = s.replace(...)is intuitive but very slow. - •Comparing K chars on every character: if the pushed char differs from the bomb's last char, skip the comparison to shave the constant.
See It in Action on AlgoNote
Watch characters stack up one by one and pop the moment the tail matches the bomb pattern, step by step on AlgoNote.