Remove Duplicate Letters

Remove Duplicate Letters

What is this problem about?

The Remove Duplicate Letters interview question asks you to remove duplicate characters from a given string so that each character appears exactly once, while the resulting string is the smallest possible in lexicographical order. Crucially, you must preserve the relative order of characters. This problem is a classic application of the monotonic stack and greedy strategy on strings.

Why is this asked in interviews?

This problem is a staple at Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg because it requires combining multiple concepts: greedy decision-making, a monotonic stack for maintaining lexicographic order, and frequency tracking to know when it is safe to discard a character. It closely models real-world problems like data deduplication, compiler symbol table management, and encoding optimizations.

Algorithmic pattern used

The pattern is a monotonic stack with greedy character selection. First, compute the frequency of each character. Then iterate through the string with a stack and a "seen" set. For each character: if it's already in the stack (seen), skip it. Otherwise, while the stack is non-empty, the top of the stack is greater than the current character, and the top character still appears later in the string (frequency > 0), pop the top and mark it unseen. Then push the current character and mark it seen. Decrement the frequency at each step.

Example explanation

Input: "bcabc" Frequencies: b=2, c=2, a=1.

• 'b': stack=[b], seen={b}, freq: b=1
• 'c': stack=[b,c], seen={b,c}, freq: c=1
• 'a': 'c' > 'a' and freq[c]=1 > 0 → pop 'c'. 'b' > 'a' and freq[b]=1 > 0 → pop 'b'. Push 'a'. stack=[a], seen={a}
• 'b': push. stack=[a,b], freq: b=0
• 'c': push. stack=[a,b,c]

Result: "abc".

Common mistakes candidates make

• Not tracking whether a character is already in the stack — leading to duplicate characters in the result.
• Forgetting to decrement frequency before checking if a pop is safe.
• Popping a character from the stack when it won't appear again later, making it impossible to include later.
• Confusing this problem with simply sorting the unique characters.

Interview preparation tip

For the Remove Duplicate Letters coding problem, the monotonic stack and greedy interview pattern is the key. Before coding, write out the frequency map and trace through the stack operations manually on a small example. Interviewers at DRW and TikTok often probe the "why can we pop?" condition — be ready to explain that you can only remove a character from the stack if it appears again later in the string.