Remove Duplicate Letters

Remove Duplicate Letters asks you to keep each letter exactly once and make the result as small as possible alphabetically. It is the classic problem for the greedy monotonic stack — the move where you eagerly drop a character now because you know you can grab it again later.

The slow way first

You could generate every subsequence that contains each letter once and pick the smallest. That is exponential — hopeless. Even a smarter approach that re-scans the remaining string for the best next letter at every position is O(n²).

The question to ask: while I am building the answer left to right, when is it safe to throw away a letter I already placed? If the letter I placed is bigger than the one I am holding now, and it shows up again later, then dropping it makes the answer smaller and I lose nothing — I can re-add it later.

The idea: a greedy monotonic stack

Walk the string once, building the answer on a stack. For each character c:

• If c is already on the stack, skip it — we only want one copy.
• Otherwise, while the top of the stack is bigger than c and that top letter occurs again later in the string, pop it. Popping a bigger letter that we can recover later shrinks the answer.
• Then push c.

The "occurs again later" check uses a precomputed last-occurrence index for each letter.

The stack always stays as small (alphabetically) as it safely can, so when we join it at the end we get the lexicographically smallest valid string.

Walk through it

Step through the animation on "bcabc". Push b, push c. When we hit a, both c and b are bigger than a and both appear again later, so we pop them. We push a, then re-add b and c later. The stack ends as [a, b, c] → "abc".

Pseudocode

last = last index where each letter appears in s
stack = empty list, in_stack = empty set
for each letter c in s:
    if c is in_stack:            # already placed, skip
        continue
    while stack is not empty and top > c and last[top] > current index:
        pop the top and remove it from in_stack
    push c, add c to in_stack
return the stack joined into a string

The Python solution

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

• last maps each letter to the last index it appears at — our "does it occur again later?" oracle.
• in_stack is a set so the c in in_stack skip check is O(1).
• Line 7 is the greedy heart: pop the top only if it is bigger than c and last[top] > i, meaning we can still recover it later.
• We push c and record it in in_stack; the join at the end produces the final string.

Complexity

The alphabet is fixed (26 letters), so the stack and set hold at most 26 entries — effectively O(1) extra space. Each character is pushed and popped at most once, giving a single linear pass.

When this pattern shows up

Practice