Remove Duplicate Letters: Greedy Monotonic Stack

316. Remove Duplicate Letters gives you a string s and asks you to remove duplicate letters so that every letter appears exactly once, and the result is the lexicographically smallest string among all valid results. You cannot reorder the remaining letters; you can only delete some of them.

For example: "bcabc" becomes "abc", and "cbacdcbc" becomes "acdb". The second example is trickier than it looks — "abcd" seems smaller, but you cannot achieve it because after choosing 'a' and 'b' early, the only 'd' appears before the only remaining 'c', so you are forced into "acdb".

The approach: greedy monotonic stack

The key insight is this: when you encounter a character that is smaller than the top of your current result stack, you should pop the top — but only if that top character appears again later in the string. If it does not appear later, you can never recover it, so you must keep it.

That gives you two conditions that must both be true before you pop:

1. The top of the stack is greater than the current character.
2. The top character still appears later in the string (it will get another chance).

If either condition fails, you stop popping and push the current character instead. You also skip any character that is already in your result stack, because adding it again would create a duplicate.

Before iterating, build a last_occurrence map that stores the last index where each character appears. This lets you check condition 2 in O(1).

Here is the full algorithm:

• Build last = {c: last index of c in s} for all characters.
• Maintain a stack (your result so far) and a seen set for O(1) membership checks.
• For each character c at index i:
  • If c is already in seen, skip it.
  • Otherwise, while the stack is non-empty and the top is greater than c and last[top] > i, pop the top and remove it from seen.
  • Push c and add it to seen.
• Join the stack into a string.

def removeDuplicateLetters(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)

Complexity

Time is O(n) because each character is pushed onto the stack at most once and popped at most once, so the total number of push and pop operations across the entire loop is bounded by 2n. The last map and the seen set both hold at most 26 entries (the lowercase alphabet), so space is O(1) regardless of input length.

The building blocks

Monotonic stack pattern. The stack maintains a specific order invariant. Here, the invariant is that the stack stays in increasing lexicographic order as long as popping is allowed. This is the same mechanical idea as Daily Temperatures, where you pop indices off the stack when you find a warmer day. The difference is that Daily Temperatures uses a strictly decreasing stack on temperatures, while this problem uses a strictly increasing stack on characters.

Greedy invariant. The reason you can pop is that replacing a larger character with a smaller one always produces a lexicographically better result at that position, and the greedy choice is locally and globally optimal here. The condition last[top] > i is what makes the greedy safe: it guarantees you will still be able to include that character in the result later.

Seen set for deduplication. The seen set is what prevents you from adding the same character twice. Without it, you would push duplicate characters and violate the problem constraint. It mirrors the same role that a visited set plays in graph traversal.

Edge cases

• Single character: The loop runs once, pushes the character, and returns it immediately.
• All same character (e.g., "aaaa"): Every character after the first is already in seen, so they are all skipped. You return just "a".
• Already sorted (e.g., "abc"): No character is ever greater than the one that follows it, so no pops occur. The stack fills up in order and the output equals the first occurrence of each letter.
• Reverse sorted, each appearing once (e.g., "cba"): No character reappears, so last[top] > i is never true. No pops occur. The output is the full input "cba" — you cannot improve on it.

From understanding to recall

The logic is easy to follow when you trace through it step by step. What is easy to forget under pressure is the exact pair of conditions that must hold simultaneously before you pop.

The two conditions are:

1. stack[-1] > c — the top is lexicographically larger than the current character.
2. last[stack[-1]] > i — the top will appear again later (so we are not losing it forever).

Miss the first condition and you destroy the increasing order of your result. Miss the second condition and you silently drop a character that never comes back, making the output invalid.

Practicing this problem with spaced repetition trains you to write both conditions automatically, without having to reconstruct the reasoning from scratch each time.

Related posts

• Daily Temperatures - The canonical monotonic stack problem; same pop-when-better mechanics applied to temperatures
• Largest Rectangle in Histogram - Another monotonic stack problem where the condition to pop is crossing a boundary height
• Stack Patterns - A guide to recognizing when a monotonic stack is the right tool