Remove Duplicate Letters
Understanding the Problem
The phrase "remove duplicates" makes this sound easy, but the lexicographical ordering requirement is what makes it hard. We cannot keep the first occurrence of each letter, because that might not give the smallest result. In "cbabc", first occurrences give "cba", but the smallest valid answer is "abc".
The constraints define what counts as a valid answer. We select exactly one occurrence of each distinct character, and the selected characters keep their relative order from the original string, so the result is a subsequence. Among all subsequences that contain every distinct letter exactly once, we want the lexicographically smallest.
This combines a greedy choice with a monotonic stack. We build the result left to right and remove a larger character we already placed whenever a smaller one comes along, provided the larger character appears again later so we can recover it.
Key Constraints:
1 <= s.length <= 10^4: An O(n^2) approach reaches 10^8 operations, which is borderline. An O(n) solution is comfortable.sconsists of lowercase English letters: there are only 26 possible characters, so a frequency array, a last-index array, and an in-stack array are all constant size.
Approach 1: Brute Force (Generate All Subsequences)
Intuition
Generate every subsequence that contains each distinct character exactly once, then pick the lexicographically smallest one.
If the string has k distinct characters, we choose one position for each character. A character may appear at several positions, so there are multiple choices per character. We try every combination, read each one in index order to form a candidate string, and keep the smallest.
This is simple to reason about but inefficient. If each character appears up to m times and there are k distinct characters, the number of combinations is up to m^k.
Algorithm
- Find all distinct characters in the string and the list of positions where each appears.
- Generate every way to pick one position for each distinct character.
- For each combination, sort the chosen positions in increasing order and read the characters in that order to form a candidate string.
- Return the lexicographically smallest candidate.
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 and discards almost all of them. The next approach builds the answer in a single pass, making a greedy choice at each character that is provably optimal.
Approach 2: Greedy with Monotonic Stack
Intuition
We build the result one character at a time, keeping it as a subsequence, and want the earliest positions of the result to hold the smallest characters possible.
While scanning left to right, we hold the result so far on a stack. When the current character is smaller than the character on top of the stack, removing the top would make the result lexicographically smaller. That removal is safe only when the top character appears again later in the string, since we can add it back when we reach that later occurrence. If the top character does not appear again, removing it would drop it from the answer entirely, so we leave it in place.
A monotonic stack captures this rule directly: pop the top while it is larger than the current character and appears later. To keep each character exactly once, we skip the current character if it is already on the stack.
A pop happens only when the top character is larger than the current one and reappears later. Replacing the larger character at an earlier position with the smaller one produces a lexicographically smaller prefix, and the popped character is still available downstream, so no required letter is lost. A character is never popped once it is at its last occurrence, because the condition lastIndex[top] > i fails, so every distinct letter survives to the final stack.
Each character is pushed at most once and popped at most once. The total number of push and pop operations across the whole scan is therefore O(n).
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.