Remove Duplicate Letters
Remove Duplicate Letters: delete characters so every letter appears exactly once, and among all such results return the lexicographically smallest.
- 1 <= s.length <= 10⁴
- s consists of lowercase English letters
Intuition
Reading left to right, a letter already placed should be given up whenever it is larger than the incoming letter and it still occurs later — swapping it out lowers the result and loses nothing. That is a monotonic stack with one extra condition: a letter may only be popped if a future copy exists to replace it. Remaining-count information is therefore as essential as the stack itself.
A monotonic stack applies whenever a result is built left to right and an earlier choice can be revoked once a better one arrives. The extra ingredient here is a feasibility check on the pop. Remove K Digits is the same structure with a pop budget instead of remaining counts.
Approach
Before reading on: work out the exact condition under which a letter already placed may be given up. Then find the input where popping a larger letter would make the answer invalid rather than smaller.
The greedy exchange that makes it lexicographic
Comparing strings of equal length is decided by the earliest differing position, so making an early character smaller always wins, regardless of what follows. If the stack ends with c and the incoming letter is b, then dropping c produces a strictly smaller prefix — provided c appears again later so it can still be included. This exchange argument is what licenses the greedy pop; without a later copy the swap would lose a required letter and the result would be invalid rather than merely larger.
Two pieces of state: remaining counts and an in-stack set
Precompute how many times each letter still occurs at or after the current position — a countdown decremented as the scan advances. Also maintain a set of letters currently on the stack. When a letter arrives that is already in the stack, skip it entirely: it is placed, and every valid answer contains exactly one copy. Otherwise pop while the top is larger than the incoming letter and its remaining count is positive, then push. The set prevents duplicates; the counts prevent popping a letter that will never return.
Why the result is both valid and minimal
Validity holds because a letter is only popped when a later occurrence is guaranteed, and the set ensures exactly one copy of each distinct letter ends up placed. Minimality follows from the exchange argument applied at every step: the stack is kept as small as possible at each position without sacrificing a needed letter, and any lexicographically smaller string would require making some earlier position smaller, which the greedy already attempted. Each character is pushed and popped at most once, giving O(n) time and O(26) space.
Solution & live demo
Common pitfalls
Popping without checking the remaining count
while stack and ch < stack[-1]:
in_stack.remove(stack.pop())while stack and ch < stack[-1] and remaining[stack[-1]] > 0:
in_stack.remove(stack.pop())If the letter on top has no later occurrence, popping it removes it from the answer permanently. On "bac" the b would be dropped and never restored, producing an invalid result missing a required letter.
Decrementing the count after the skip
if ch in in_stack:
continue
remaining[ch] -= 1remaining[ch] -= 1
if ch in in_stack:
continueThe count must reflect occurrences strictly ahead of the current position for every character, including skipped ones. Decrementing late leaves a stale count that can permit an unsafe pop.
Re-pushing a letter already in the stack
stack.append(ch)
if ch in in_stack:
continue
stack.append(ch)Each distinct letter must appear exactly once. Without the membership check the stack accumulates repeats and the output violates the problem's core requirement.
Edge cases
No pop ever fires and the string is returned unchanged.
The first is pushed and the rest are skipped as already present.
Its remaining count is 0, so it is not popped even though it exceeds the incoming letter.
Each new letter pops the previous ones when later copies exist.
Pushed once and returned.