Skip to content

visual walkthrough

Remove Duplicate Letters

MediumMonotonic Stack (Greedy)Reported at: AppleAmazonMeta+1

Greedy monotonic stack with 'last occurrence' look-ahead.

Solve on LeetCode

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

approachtimespace
Monotonic stack + last seenO(n)O(1)

More walkthroughs