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 <= 104s consists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
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.
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.
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.
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.
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 | 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. |
| 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. |
Remove Duplicate Letters | Leetcode #316 • Techdose • 36,353 views views
Watch 9 more video solutions →Practice Remove Duplicate Letters with our built-in code editor and test cases.
Practice on FleetCode