Remove Duplicate Letters
Problem Statement
Given a lowercase string s, remove duplicate letters so that every distinct letter appears exactly once. Among all valid results, return the lexicographically smallest one.
Input
A lowercase string s.
Output
The lexicographically smallest string that contains each distinct character from s exactly once.
Constraints
- •
1 <= s.length <= 10^4 - •
s consists of lowercase English letters
Examples
Example 1
s = bcabc
abcExample 2
s = cbacdcbc
acdbLearning Objectives
- Use remaining occurrence counts to decide whether a chosen character can be safely removed.
- Maintain a monotonic increasing stack for lexicographic minimisation under subsequence constraints.
- Distinguish between a character that is larger and removable and one that is larger but mandatory now.
- Prove stack pops with an exchange argument based on a later replacement copy.
Intuition
Greedy Insight: Build the answer left to right with a monotonic increasing stack. When a smaller character arrives, it should move as far left as possible. You may pop a larger top character only if that larger character appears again later, because then it can be reinserted without losing required coverage.
The key is the future count. A larger top with no remaining copy is locked in place. A larger top with a remaining copy is safe to postpone, and postponing it makes the prefix smaller immediately, which is exactly what lexicographic order rewards.
Common mistakes
- ×Popping a larger character without checking whether it appears again later, which can remove a required letter permanently.
- ×Sorting the distinct characters, which ignores the subsequence order constraint imposed by the original string.
- ×Forgetting to mark a popped character as not currently in the stack.
- ×Skipping duplicate characters before decrementing their remaining count, which makes future-availability decisions wrong.
Algorithm Explanation
Greedy strategy Scan left to right while maintaining a stack that is as lexicographically small as possible. Before deciding on the current character, decrement its remaining count. If it is already in the stack, skip it. Otherwise, while the stack top is larger than the current character and the top appears later again, pop the top. Then push the current character.
Why it works Lexicographic order is decided by the earliest position where two answers differ. If a smaller current character can replace a larger stack top while the larger character can still be placed later, the replacement strictly improves the answer without sacrificing feasibility.
Proof of correctness Assume an optimal valid subsequence differs from the greedy stack at the first position where greedy chose a smaller character x after popping a larger character y. Since y has another occurrence later, exchange the earlier y with x and place y at that later occurrence. The result still contains every character once and respects original order, but its first differing character is smaller, so it is lexicographically no worse. Repeating this exchange justifies every pop the greedy stack performs. Characters with no later occurrence are never popped, preserving feasibility.
Algorithm
- Count remaining occurrences of each character.
- Keep a stack-like StringBuilder and a boolean array inStack.
- For each character, decrement its remaining count.
- If it is already present, skip it.
- While the stack top is larger and has remaining copies, pop it and clear its presence flag.
- Push the current character and mark it present.
- Return the stack as the final string.
Solutions
Solution: Monotonic stack with remaining counts
The stack stores the current best answer prefix. Remaining counts answer the only safety question: if a larger top is popped, can it still appear later? This gives a single-pass greedy algorithm.
Step-by-step
- Count all characters so future availability is known during the scan.
- For each character, first reduce its remaining count because the current copy is being consumed.
- If the character is already in the stack, ignore this copy.
- Otherwise, pop larger stack-top characters while they still have future copies.
- Append the current character and mark it as present.
- Convert the stack builder to the answer string.
O(n)
O(1)
Each character is pushed and popped at most once. The count and presence arrays have 26 entries.
Java implementation
Dry Run
Sample input
s = cbacdcbc. Initial counts are c:4, b:2, a:1, and d:1.
| index | char | remaining after decrement | stack before | decision | stack after |
|---|---|---|---|---|---|
| 0 | c | c:3 | empty | Push c | c |
| 1 | b | b:1 | c | Pop c because c is larger and appears later, then push b | b |
| 2 | a | a:0 | b | Pop b because b is larger and appears later, then push a | a |
| 3 | c | c:2 | a | Push c after a | ac |
| 4 | d | d:0 | ac | Push d because stack remains increasing enough | acd |
| 5 | c | c:1 | acd | Skip c because it is already in the stack | acd |
| 6 | b | b:0 | acd | Cannot pop d because d has no later copy, so push b | acdb |
| 7 | c | c:0 | acdb | Skip c because it is already in the stack | acdb |
The final stack is acdb. The important locked decision is keeping d before b, because d has no remaining copy when b arrives.
Interview Tips
Name both conditions in the while loop out loud: the top must be lexicographically larger, and it must appear again later. Many candidates remember the monotonic stack but forget the feasibility condition. A strong proof says that every pop improves the earliest possible character while preserving a later copy of the popped letter.
Likely follow-ups
- How would the algorithm change for the related problem Smallest Subsequence of Distinct Characters?
- What if the input alphabet is not limited to lowercase English letters?
- How would you return the largest lexicographic valid result instead?
- What if each character must appear at most twice rather than exactly once?
Similar Problems
Key Takeaways
- Lexicographic minimisation is about improving the earliest possible position.
- A larger stack top can be removed only when a future copy preserves feasibility.
- The stack is monotonic only as far as the remaining-count constraint allows.
- Each character enters and leaves the stack at most once, giving a linear solution.