Remove Duplicate Letters
Last Updated: March 29, 2026
Understanding the Problem
At first glance, this problem might look like a simple "remove duplicates" task, but the lexicographical ordering requirement is what makes it tricky. We cannot just take the first occurrence of each letter, because that might not give us the smallest result. For example, in "cbabc", taking first occurrences gives "cba", but the answer is "abc".
We need to select exactly one occurrence of each distinct character, and the characters we pick must appear in the same relative order as in the original string (it is a subsequence). Among all such valid subsequences, we want the lexicographically smallest one.
The key insight is that this is a greedy problem with a monotonic stack flavor. At each position, we want to keep the result as small as possible by removing larger characters from our answer, but only when we know those characters appear again later in the string.
Key Constraints:
1 <= s.length <= 10^4--> An O(n^2) approach would give at most 10^8 operations, which is borderline. O(n) or O(n log n) is preferred.sconsists of lowercase English letters --> Only 26 possible characters. This means frequency arrays and boolean arrays are O(1) in space.
Approach 1: Brute Force (Generate All Subsequences)
Intuition
The most straightforward way to think about this: generate every possible subsequence that contains each distinct character exactly once, then pick the lexicographically smallest one.
If the string has k distinct characters, we need to choose exactly one position for each character. For each character, there might be multiple positions to choose from. We try every combination and keep the smallest valid subsequence.
This is conceptually simple but wildly inefficient. If a character appears m times and we have k distinct characters, the number of combinations can blow up fast.
Algorithm
- Find all distinct characters in the string and their positions.
- Generate all possible ways to pick one position for each distinct character.
- For each combination, check that the selected positions form a valid subsequence (positions are in increasing order).
- Among all valid subsequences, return the lexicographically smallest one.
Example Walkthrough
Code
- Time Complexity: O(m^k * k log k) where m is the max frequency of any character and k is the number of distinct characters. For each of the k characters, we try up to m positions, giving m^k combinations. For each, we sort k positions in O(k log k).
- Space Complexity: O(n + k). O(n) for storing positions, O(k) for the recursion stack and chosen array.
The brute force explores an exponential number of combinations, doing huge amounts of wasted work by not making smart choices along the way. What if instead of trying all possibilities, we built the answer one character at a time, always making the greedily best choice?
Approach 2: Greedy with Monotonic Stack
Intuition
Here is the key observation: we want the lexicographically smallest result, and we are building a subsequence. Think of it as building a string character by character. At each step, we want the smallest character possible at each position.
Imagine you are building the result left to right. You have already added some characters. Now you see a new character that is smaller than the last character in your result. Should you keep the last character or remove it? That depends on one thing: does the last character appear again later in the string? If yes, you can safely remove it now and pick it up later. If no, you are stuck with it.
This "remove the top if it is larger and appears later" logic is exactly what a monotonic stack does. The stack maintains characters in a way that keeps the result as small as possible, while ensuring we do not permanently lose any character we need.
We also need to avoid adding a character that is already in the stack, since we want each character exactly once.
The greedy strategy works because of two properties. First, we always try to make the current position as small as possible by removing larger characters that appear later. This is safe because we can always pick those characters up again. Second, the inStack check ensures we never add a duplicate, and once a character is locked in (because it was its last occurrence), it stays permanently.
The monotonic stack naturally maintains the invariant that our result is the lexicographically smallest valid subsequence at every step. Each character is pushed at most once and popped at most once, so the stack operations across the entire loop are O(n) total.
Algorithm
- Count the frequency of each character in the string (or record the last index of each character).
- Initialize an empty stack and a boolean array tracking which characters are currently in the stack.
- Iterate through each character in the string:
- If the character is already in the stack, skip it.
- Otherwise, while the stack is not empty, and the top of the stack is greater than the current character, and the top character appears later in the string (last index > current index), pop the top and mark it as not in the stack.
- Push the current character onto the stack and mark it as in the stack.
- The stack contains the answer.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the string once. Each character is pushed onto and popped from the stack at most once, so the total work across all push and pop operations is O(n). Computing last indices is also O(n).
- Space Complexity: O(1). The stack, inStack array, and lastIndex array all have at most 26 entries (for lowercase English letters). This is constant space relative to input size.