Remove Duplicate Letters
Problem Description
Question
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 <= 104
sconsists of lowercase English letters.
Solve it on LeetCode
Approaches
1. Greedy approach with Stack and HashMap
Intuition:
The task is to remove duplicate letters and return the lexicographically smallest result. To achieve this, we need to ensure that for each character, we decide whether to keep it or remove it based on its placement and frequency.
Steps:
- Use a HashMap to record the last occurrence of each character in the string. This helps us determine if a character can be safely removed when traversing the string.
- Use a Stack to build the result string.
- Use a boolean array to keep track of characters in the current stack to prevent duplicates.
- Traverse each character in the string:
- If the character is already in the stack, skip it.
- Otherwise, compare it with the top of the stack, and if the top character appears later, and the current character is smaller, pop the stack.
- Push the current character onto the stack and mark it in the boolean array.
- Convert the stack into the resulting string.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string, as we are iterating through the string and each character is pushed and popped from the stack at most once.
- Space Complexity: O(1), since the size of the alphabet is fixed. The stack will at most contain 26 characters.
2. Optimized Greedy with Char Array as Stack
Intuition:
Instead of using a stack data structure, we can use a character array to simulate stack behavior. This slight optimization can lead to performance improvements by reducing method call overheads of Stack operations.
Steps:
- Follow similar logic to the stack-based approach, managing character presence using an array.
- Use a
char[]array to act as a stack, managing a pointer to simulate stack-like push/pop operations.
Code:
Complexity Analysis
- Time Complexity: O(n), similar to the previous approach.
- Space Complexity: O(1), as we utilize constant additional space in line with the alphabet's size.