Remove Duplicate Letters — Solution

Problem

Given a string of lowercase letters, remove extra copies of each character so that every letter appears exactly once in the result. Among all strings that satisfy this constraint, return the one that comes first in lexicographic (alphabetical) order.

• Input: s = "bcabc"
• Output: "abc"
• Explanation: every letter appears once, and "abc" is smaller than any other valid arrangement like "bca" or "cab".

Counter-example: s = "cbacdcbc" → "acdb", not "abcd". The 'd' must appear before the second 'c' because after position 4 (the first 'd') there are no more 'd's left — so 'd' cannot be pushed to the end.

Intuition

We're building a subsequence of the input that contains each distinct character exactly once, and we want it to be as small lexicographically as possible. The greedy insight: whenever we see a character that is smaller than the most recently placed character, we can evict that larger character from our result — but only if it still appears somewhere later in the string, giving us a chance to include it again. A monotonic stack tracks this state in a single pass.

Solution — Greedy Monotonic Stack

Count how many times each character appears in the whole string. Walk left to right: skip characters already placed in the result; otherwise, pop characters from the top of the result that are larger than the current character while they still have future occurrences available. Then place the current character.

1. Build a frequency map of every character in the string.
2. Maintain a stack (the growing result) and an in_stack set tracking which characters are already placed.
3. For each character c, decrement its remaining count — this occurrence is now consumed.
4. If c is already in in_stack, skip it; it has already been placed at an optimal position.
5. While the top of the stack is greater than c and the top character still has future occurrences (remaining_count[top] > 0), pop it from the stack and remove it from in_stack.
6. Push c onto the stack and record it in in_stack.
7. Join the stack into the final answer.

1def removeDuplicateLetters(s: str) -> str:
2    remaining_count = {}
3    for char in s:
4        remaining_count[char] = remaining_count.get(char, 0) + 1
5
6    stack = []
7    in_stack = set()
8
9    for char in s:
10        remaining_count[char] -= 1  # this occurrence is now behind us
11
12        if char in in_stack:
13            continue  # already placed at the best earlier position
14
15        # evict larger characters that can be added again later
16        while stack and stack[-1] > char and remaining_count[stack[-1]] > 0:
17            in_stack.discard(stack.pop())
18
19        stack.append(char)
20        in_stack.add(char)
21
22    return "".join(stack)

Time: O(n) — each character is pushed and popped at most once across the entire loop.

Space: O(1) — the stack and in-stack set hold at most 26 distinct characters regardless of input length.

Complexity Summary

Common Mistakes

• Popping when remaining_count[top] == 0: if a character has no future occurrences, it must stay in the result — evicting it means it can never be re-added, producing an incomplete string.
• Skipping the in_stack check: without tracking which characters are already placed, the same character can be pushed multiple times, producing duplicates in the output.
• Decrementing count after the stack logic: the count must be decremented before checking whether to pop, so that remaining_count reflects occurrences strictly after the current position.
• Checking remaining_count[char] instead of remaining_count[stack[-1]]: the pop condition evaluates whether the top character has a future chance to reappear — not whether the current character does.
• Forgetting to update in_stack when popping: if a popped character stays in in_stack, it will be silently skipped on its next occurrence and never placed in the result.

Related Problems

• remove-k-digits — same greedy monotonic stack pattern applied to digits to minimize a number
• largest-rectangle-in-histogram — monotonic stack tracks left and right boundaries of each bar
• next-greater-element-ii — monotonic stack finds the next larger value in a circular array
• decode-string — stack unwinds nested encoded segments during string construction
• daily-temperatures — monotonic stack computes the next warmer day for every position