Remove Duplicate Letters

Intuition

We want small letters as early as possible, but we can only drop a letter if it will show up again later. Precompute the last index at which each letter occurs. Walk the string keeping a stack of chosen letters; if the current letter is already on the stack, skip it. Otherwise, while the top of the stack is a larger letter that appears again after the current position, pop it because a better placement exists later. Push the current letter and mark it present. The stack read bottom to top is the lexicographically smallest valid string.

Algorithm walkthrough

1. 1Record the last occurrence index of every character in s.
2. 2Maintain a stack of chosen characters and a set marking which characters are currently on the stack.
3. 3For each character c at index i, if c is already on the stack, do nothing and move on.
4. 4Otherwise, while the stack top is greater than c and that top character appears again later (its last index is greater than i), pop it and clear it from the set.
5. 5Push c, mark it present, and after the scan join the stack from bottom to top to form the answer.

Implementation

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        stack = []
        seen = set()
        for i, c in enumerate(s):
            if c in seen:
                continue
            while stack and stack[-1] > c and last[stack[-1]] > i:
                seen.discard(stack.pop())
            stack.append(c)
            seen.add(c)
        return "".join(stack)