Watch 10 video solutions for Remove Duplicate Letters, a medium level problem involving String, Stack, Greedy. This walkthrough by Techdose has 30,125 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |