This problem requires producing the smallest lexicographical string with unique letters by carefully managing a stack of candidates. GhostInterview guides you to track the last occurrence of each character, decide when to pop from the stack, and avoid losing required letters. It emphasizes stack-based state management to ensure correctness and efficiency for every input string scenario.
Problem Statement
Given a string s consisting of lowercase English letters, remove duplicate letters so that each letter appears exactly once. You must return the result that is the smallest in lexicographical order among all possible results while preserving relative character order.
For example, given s = "bcabc", the correct output is "abc". For s = "cbacdcbc", the correct output is "acdb". Constraints: 1 <= s.length <= 10^4, s consists only of lowercase letters.
Examples
Example 1
Input: s = "bcabc"
Output: "abc"
Example details omitted.
Example 2
Input: s = "cbacdcbc"
Output: "acdb"
Example details omitted.
Constraints
- 1 <= s.length <= 104
- s consists of lowercase English letters.
Solution Approach
Use a Stack to Build the Result
Initialize an empty stack and a frequency map of characters. Iterate through s, and for each character, pop stack elements that are greater than the current character if they appear later again. Push the current character if it's not already in the stack to maintain unique letters.
Greedy Lexicographical Choice
At each step, choose to remove letters from the stack only if a smaller letter can safely take their place later. This ensures the final string is the lexicographically smallest while still containing all unique letters exactly once.
Optimize Membership Checks
Maintain a set or bit-mask to track letters already in the stack to avoid duplicates. This avoids unnecessary stack pushes and guarantees O(n) time complexity since each letter is pushed and popped at most once.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(k) where k is the number of unique letters, to store the stack, frequency map, and membership tracking set.
What Interviewers Usually Probe
- Watch if the candidate correctly handles repeated letters and maintains order.
- Check if they can justify the greedy lexicographical choice at each stack operation.
- Look for efficient membership tracking to prevent duplicate insertion into the stack.
Common Pitfalls or Variants
Common pitfalls
- Pushing duplicates onto the stack instead of tracking existing letters.
- Failing to pop characters when a smaller character appears later, leading to a non-optimal result.
- Ignoring the last occurrence check, which can remove needed letters and break correctness.
Follow-up variants
- Modify to allow uppercase letters and mixed case while still removing duplicates lexicographically.
- Return the largest lexicographical order string instead of the smallest.
- Apply the same stack-based approach to arrays of integers with unique selection constraints.
How GhostInterview Helps
- Automatically tracks last occurrences and stack membership to guide correct pops and pushes.
- Highlights the exact step where adding a character may violate lexicographical minimality.
- Provides immediate feedback if a duplicate or incorrect order is about to be included in the stack.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the key pattern to solve Remove Duplicate Letters efficiently?
The key pattern is stack-based state management combined with greedy lexicographical choices, ensuring each letter is added once in the minimal order.
How does GhostInterview handle duplicate tracking?
It uses sets or bit-masks to monitor which characters are already in the stack, preventing duplicates and ensuring unique inclusion.
Why is popping from the stack necessary?
Popping allows replacing larger letters with smaller ones that appear later, maintaining the lexicographical minimality required by the problem.
What is the time complexity of the solution?
The algorithm runs in O(n) time since each character is pushed and popped at most once, with membership checks in O(1) using a set or bit-mask.
Can this method be applied to similar problems?
Yes, any problem requiring unique elements in optimal order with stack-based management or greedy selection can use the same approach.
Need direct help with Remove Duplicate Letters instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Remove Duplicate Letters from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Remove K Digits requires selecting which digits to drop using a monotonic stack for the smallest possible integer result efficiently.
Open problem page#1081 Smallest Subsequence of Distinct CharactersThe Smallest Subsequence of Distinct Characters problem asks you to find the lexicographically smallest subsequence of a string with distinct characters.
Open problem page#321 Create Maximum NumberCreate Maximum Number involves merging digits from two arrays while preserving order, maximizing the resulting number.
Open problem page