visual walkthrough
Remove Duplicate Letters
Greedy monotonic stack with 'last occurrence' look-ahead.
The idea
You want each letter once, in the smallest possible order. Add letters left to right; if a smaller letter arrives and the letter on top appears again later, drop the top now because it can be added again later in a better place.
Never drop a letter whose last occurrence has passed, or it would be lost for good.
Complexity
| approach | time | space |
|---|---|---|
| Monotonic stack + last seen | O(n) | O(1) |