Remove Duplicate Letters - Solution & Explanation
Problem Statement
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: s = "bcabc" Output: "abc"
Example 2:
Input: s = "cbacdcbc" Output: "acdb"
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Approach Overview
Problem Overview: Given a string s, remove duplicate characters so every letter appears exactly once while keeping the result as the smallest possible lexicographical string. The relative ordering constraints of the original string still matter, so you cannot freely reorder characters.
Approach 1: Greedy and Stack (O(n) time, O(1) space)
This approach uses a stack to build the result while maintaining lexicographical order. First record the last occurrence index of every character. Then iterate through the string and maintain a visited set. For each character, pop elements from the stack while the current character is smaller than the stack top and the stack top appears later in the string. This greedy decision ensures the final string remains lexicographically minimal. The stack effectively becomes a monotonic stack that enforces increasing order when possible.
Approach 2: Iterative Result String Construction (O(n) time, O(1) space)
This method builds the answer string directly instead of using an explicit stack structure. Iterate through characters and maintain a result string along with a visited map. When a new character arrives, repeatedly remove the last character from the result if it is lexicographically larger and appears again later in the string. Then append the current character and mark it as used. This follows the same greedy principle as the stack approach but uses string operations instead of a dedicated stack data structure. The algorithm still scans the input once and uses constant extra memory for character tracking.
Recommended for interviews: The greedy stack solution is the expected answer. Interviewers want to see that you track the last occurrence of each character and maintain a lexicographically minimal structure while iterating once through the string. Understanding how the greedy decision interacts with stack popping demonstrates strong algorithmic reasoning. The iterative string version shows the same logic but the explicit stack version is easier to explain during interviews.
Approach 1: Approach 1: Greedy and Stack
This approach uses a stack to build the resultant string such that it is the smallest lexicographical order. We will also use an array to keep count of each character’s frequency and a boolean array to track the characters that have been added to the stack. As we iterate over each character, we decide whether to add it to the stack or skip it based on the frequency and lexicographical conditions.
The code iterates through the string, keeping track of character frequencies and deciding whether to add each character to a stack based on lexicographical ordering and frequency constraints. Characters are popped from the stack if they have occurred later, are greater than the current character, and are not the last occurrence.
Complexity
Time Complexity: O(n), where n is the length of the string, as each character is pushed and popped from the stack at most once.
Space Complexity: O(1), because the stack contains at most 26 characters, and other auxiliary data structures are of constant size.
Approach 2: Approach 2: Iterative with Result String Construction
This approach focuses on iteratively constructing the result string while ensuring that the result remains lexicographically smallest by checking each character and including it in the result only if it meets certain frequency and order criteria.
In this solution, a character set is updated via a general loop to progressively add elements to the result string. This method leverages frequency checks of character availability while ensuring characters are not redundant in the result.
Complexity
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), considering character storage is bounded to a maximum of 26.
Approach 3: Stack
We use an array last to record the last occurrence of each character, a stack to save the result string, and an array vis or an integer variable mask to record whether the current character is in the stack.
Traverse the string s, for each character c, if c is not in the stack, we need to check whether the top element of the stack is greater than c. If it is greater than c and the top element of the stack will appear later, we pop the top element of the stack and push c into the stack.
Finally, concatenate the elements in the stack into a string and return it as the result.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Approach 4: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy and Stack | Time Complexity: O(n), where n is the length of the string, as each character is pushed and popped from the stack at most once. |
| Approach 2: Iterative with Result String Construction | Time Complexity: O(n), where n is the length of the input string. |
| Stack | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy + Monotonic Stack | O(n) | O(1) | Best general solution. Clear logic for maintaining smallest lexicographic order while ensuring each character appears once. |
| Iterative Result String Construction | O(n) | O(1) | Useful when implementing without an explicit stack structure while applying the same greedy removal logic. |
Video Solution
Remove Duplicate Letters | Leetcode #316 • Techdose • 37,770 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Duplicate Letters easy or hard?
Remove Duplicate Letters Python/Java solution
How to solve Remove Duplicate Letters in O(n)?
What is the best approach for Remove Duplicate Letters?
Is Remove Duplicate Letters asked at Google/Amazon/Meta?
What data structure is used in Remove Duplicate Letters?
What is the time complexity of Remove Duplicate Letters?
Ready to solve this problem?
Practice Remove Duplicate Letters with our built-in code editor and test cases.
Practice on FleetCode