Remove Duplicate Letters — Monotonic Stack + Greedy Solution

Given a string, remove duplicate letters so that every letter appears exactly once and the result is the smallest in lexicographic order among all possible results.

This is LeetCode 316 (also known as LeetCode 1081: Smallest Subsequence of Distinct Characters — same problem).

Understanding the Problem

Input:  "bcabc"
Output: "abc"   ← not "bca" or "cab" — "abc" is lexicographically smallest

Input:  "cbacdcbc"
Output: "acdb"  ← each letter once, smallest possible order

The challenge: you cannot just sort the characters. You must maintain the relative order from the original string while picking the smallest arrangement.

The Three-Part Strategy

You need three data structures working together:

1. Stack (monotonic): Builds the result in increasing order when possible
2. Frequency counter: Knows if a character appears later, so we can safely remove it now
3. Visited set: Prevents adding a character that is already in the stack

def remove_duplicate_letters(s: str) -> str:
    """
    Remove duplicates, return lexicographically smallest result.
    LeetCode 316.
    Time: O(n), Space: O(1) — at most 26 characters
    """
    # Count remaining occurrences
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1

    stack = []
    in_stack = set()

    for char in s:
        freq[char] -= 1  # one less occurrence remaining

        if char in in_stack:
            continue  # already in result

        # Pop larger characters if they appear later
        while (stack and
               stack[-1] > char and
               freq[stack[-1]] > 0):
            removed = stack.pop()
            in_stack.remove(removed)

        stack.append(char)
        in_stack.add(char)

    return ''.join(stack)

Step-by-Step Trace: "cbacdcbc"

Frequencies: c=4, b=2, a=1, d=1

Char  freq after   in_stack?  Stack action                    Stack
────  ──────────   ─────────  ────────────                    ─────
'c'   c=3          No         push                            [c]
'b'   b=1          No         c>'b' & freq[c]=3>0 → pop c    []
                               push b                         [b]
'a'   a=0          No         b>'a' & freq[b]=1>0 → pop b    []
                               push a                         [a]
'c'   c=2          No         a<'c' → push                   [a,c]
'd'   d=0          No         c<'d' → push                   [a,c,d]
'c'   c=1          Yes!       skip (already in stack)         [a,c,d]
'b'   b=0          No         d>'b' but freq[d]=0 → STOP     [a,c,d]
                               c>'b' but freq[c]=1>0 → pop c [a,d]
                               wait — d>'b' & freq[d]=0 STOP
                               Actually: check d first.
                               d>'b' & freq[d]=0 → can't pop
                               push b                         [a,c,d,b]
'c'   c=0          Yes!       skip                            [a,c,d,b]

Result: "acdb" ✓

Let me retrace more carefully:

Initial freq: {c:4, b:2, a:1, d:1}

i=0, char='c', freq[c]=3
  Not in stack. Stack empty → push.
  Stack: [c], in_stack: {c}

i=1, char='b', freq[b]=1
  Not in stack.
  stack[-1]='c' > 'b' AND freq[c]=3 > 0 → pop c
  Stack: [], in_stack: {}
  Push b.
  Stack: [b], in_stack: {b}

i=2, char='a', freq[a]=0
  Not in stack.
  stack[-1]='b' > 'a' AND freq[b]=1 > 0 → pop b
  Stack: [], in_stack: {}
  Push a.
  Stack: [a], in_stack: {a}

i=3, char='c', freq[c]=2
  Not in stack. stack[-1]='a' < 'c' → push.
  Stack: [a,c], in_stack: {a,c}

i=4, char='d', freq[d]=0
  Not in stack. stack[-1]='c' < 'd' → push.
  Stack: [a,c,d], in_stack: {a,c,d}

i=5, char='c', freq[c]=1
  Already in stack → skip.

i=6, char='b', freq[b]=0
  Not in stack.
  stack[-1]='d' > 'b' BUT freq[d]=0 → can't pop (last d!)
  Push b.
  Stack: [a,c,d,b], in_stack: {a,c,d,b}

i=7, char='c', freq[c]=0
  Already in stack → skip.

Result: "acdb" ✓

Why Each Component Is Needed

Without frequency counter:

We might pop a character that does not appear again, losing it forever.

"abcb" — if we pop 'c' because 'b' < 'c', but 'c' never appears again → wrong!
freq[c]=0 prevents this pop.

Without visited set:

We would add duplicate characters to the result.

"bcabc" — after building [a,b], we'd add 'c', then later add 'b' again → "abcb" (duplicated b)

Without monotonic stack:

We would not achieve the smallest lexicographic order.

"bcabc" — simple dedup gives "bca" or "bac", but "abc" is smaller.
The stack's pop-if-larger logic ensures smallest order.

Complexity

The O(1) space is because the alphabet is fixed at 26 lowercase letters.

Edge Cases

# Single character
assert remove_duplicate_letters("a") == "a"

# Already no duplicates
assert remove_duplicate_letters("abc") == "abc"

# All same character
assert remove_duplicate_letters("aaaa") == "a"

# Reverse sorted
assert remove_duplicate_letters("dcba") == "dcba"  # can't reorder

# Must keep order
assert remove_duplicate_letters("abacb") == "abc"

When to Use This Pattern

• Smallest/largest subsequence: When you need the lexicographically optimal subsequence with constraints
• Character selection with ordering: Choosing characters while maintaining relative order
• Greedy + stack: Problems where local greedy decisions (pop larger) lead to global optimum

Identifying This Pattern

Look for these clues:

1. “Lexicographically smallest” or “lexicographic order”
2. “Each character exactly once”
3. “Maintain relative order”
4. Subsequence selection with optimization

Related Problems

• Remove K Digits — similar monotonic stack approach
• Monotonic Stack Guide — the underlying pattern
• Online Stock Span — another monotonic stack problem