Remove Duplicate Letters — Smallest Lexicographic Subsequence via Greedy Stack

Problem Statement#

Given a string s, remove duplicate letters so that every letter appears once and only once. The result must be the smallest in lexicographic order among all possible results.

Constraints:

• 1 <= s.length <= 10^4
• s consists of lowercase English letters only

Input:  s = "bcabc"
Output: "abc"

Input:  s = "cbacdcbc"
Output: "acdb"

Why This Problem Matters#

Remove Duplicate Letters is a medium problem that feels much harder because it combines three things simultaneously: greedy decision-making, a monotonic stack, and a look-ahead constraint (can I pop this character? Only if it appears again later). Google uses this problem to test whether candidates can reason about greedy correctness — not just code a greedy heuristic but prove it is safe.

The problem is identical to LC 1081 (Smallest Subsequence of Distinct Characters) and appears as a building block for harder problems like Create Maximum Number (LC 321) and Remove K Digits (LC 402). Understanding the "pop only if the character appears again later" constraint here is the prerequisite for those problems.

The Core Insight#

We want the result to be lexicographically smallest. Greedy strategy: whenever we see a character smaller than the stack top (current result so far), we prefer to remove the larger character and replace it with the smaller one.

The catch: we can only remove a character from the stack if it appears again later in the string. If the stack top is the last occurrence of that character, removing it would lose that character from the result entirely.

The greedy rule for each character c:

1. Skip if c is already in the stack (already selected).
2. While stack is non-empty AND c < stack[-1] AND last_occurrence[stack[-1]] > current_index: pop the stack top.
3. Push c.

The last_occurrence map, precomputed as {char: last_index}, enables the look-ahead in O(1).

Visual Dry Run#

Input: s = "cbacdcbc", last occurrences: {c:7, b:6, a:2, d:4}

Result: "acdb".

At step 6: b < d so we want to pop d, but last[d] = 4 < 6 — we have already passed the last d. Removing d here would lose it permanently, so we cannot pop.

Solution (Optimal)#

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 c < stack[-1] and last[stack[-1]] > i:
                seen.discard(stack.pop())
 
            stack.append(c)
            seen.add(c)
 
        return ''.join(stack)

var removeDuplicateLetters = function(s) {
    const last = {};
    for (let i = 0; i < s.length; i++) {
        last[s[i]] = i;
    }
 
    const stack = [];
    const seen = new Set();
 
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (seen.has(c)) continue;
 
        while (stack.length > 0 && c < stack[stack.length - 1] && last[stack[stack.length - 1]] > i) {
            seen.delete(stack.pop());
        }
 
        stack.push(c);
        seen.add(c);
    }
 
    return stack.join('');
};

Time: O(n) — each character is pushed and popped at most once Space: O(26) = O(1) — stack and seen set hold at most 26 distinct lowercase letters

Common Mistakes#

• Forgetting the seen check — without it, you add duplicates and corrupt the stack order
• Wrong pop condition — popping whenever c < stack[-1] without checking last_occurrence leads to removing characters that cannot be re-added, breaking the "all characters exactly once" constraint
• Forgetting to remove from seen when popping — if a popped character stays in seen, it will be skipped when encountered again later
• Using a frequency count instead of last_occurrence — equivalent but more complex; last_occurrence precomputation is cleaner

Interview Tips#

• State the invariant clearly before coding: "I maintain a stack that is the current best result. I greedily pop characters that are lexicographically larger than the current one, but only if the larger character still has a future occurrence."
• When asked "why is your greedy choice always correct?": "If I can replace a larger character at position j in my stack with the current smaller character, and I know the larger character will appear again later, the smaller character at j followed by the larger character later gives a strictly smaller result. This exchange argument proves the greedy is optimal."
• Walk through example 2 ("cbacdcbc") step by step during coding — it hits every edge case.

Follow-up Questions#

• What if you want the lexicographically largest subsequence instead? Reverse the comparison: pop when c > stack[-1], still with the last-occurrence guard.
• How does this relate to Remove K Digits (LC 402)? Remove K Digits also uses a monotonic stack where you pop larger digits. The difference: there the guard is budget-based (k pops allowed total); here the guard is last-occurrence-based.
• What if there is no constraint that all characters must appear exactly once? This becomes a different problem — finding the lexicographically smallest subsequence of length k requires a greedy sliding window approach.

Key Takeaways#

• Use a greedy stack with two guards: skip characters already in the stack, and only pop a character if it appears again later.
• The last_occurrence map enables the "appears again later" check in O(1) per character.
• The seen set must be updated on both push (add) and pop (remove) to track what is currently in the stack.
• The stack naturally stays lexicographically non-decreasing from bottom to top, producing the smallest valid subsequence.
• Space complexity is O(1) — there are at most 26 distinct lowercase characters, bounding both the stack and seen set.
• This problem is identical to LC 1081 (Smallest Subsequence of Distinct Characters) — the same solution applies.
• The exchange argument that proves this greedy correct also applies to Remove K Digits and Create Maximum Number (LC 321).