visual walkthrough
Remove All Adjacent Duplicates In String
Using the stack as a 'last kept character' buffer.
The idea
When two equal letters cancel, the letters on either side may become neighbours and cancel too. A stack handles this naturally: its top is always the letter just before the one being read.
Compare each new letter with the top: equal means cancel (pop), otherwise push.
Complexity
| approach | time | space |
|---|---|---|
| Rescan after each deletion | O(n²) | O(n) |
| Stack | O(n) | O(n) |