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/
The key challenge in Remove Duplicate Letters is to produce the smallest lexicographical string while ensuring each character appears only once. A common strategy combines greedy thinking with a monotonic stack. The idea is to iterate through the string and maintain a stack that stores characters of the resulting string in increasing lexicographic order.
Before pushing a new character, we check if the top of the stack is larger and if it appears again later in the string. If both conditions are true, we can safely remove it to achieve a smaller lexicographic result. To support this logic, we track the last occurrence of each character and maintain a visited set to avoid duplicates.
This approach ensures that each character is pushed and popped at most once, making the solution efficient while preserving the optimal lexicographic order.
Time Complexity: O(n) and Space Complexity: O(n), where n is the length of the string.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy + Monotonic Stack | O(n) | O(n) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
Greedily try to add one missing character. How to check if adding some character will not cause problems ? Use bit-masks to check whether you will be able to complete the sub-sequence if you add the character at some index i.
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.
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.
1#include <iostream>
2#include <string>
3#include <vector>
4#include <stack>
5using namespace std;
6
7string removeDuplicateLetters(string s) {
8 vector<int> freq(26, 0);
9 vector<bool> inStack(26, false);
10 for (char c : s) freq[c - 'a']++;
11 stack<char> result;
12 for (char c : s) {
13 freq[c - 'a']--;
14 if (inStack[c - 'a']) continue;
while (!result.empty() && result.top() > c && freq[result.top() - 'a'] > 0) {
inStack[result.top() - 'a'] = false;
result.pop();
}
result.push(c);
inStack[c - 'a'] = true;
}
string res;
while (!result.empty()) {
res = result.top() + res;
result.pop();
}
return res;
}
int main() {
string s = "cbacdcbc";
cout << removeDuplicateLetters(s) << endl;
return 0;
}In this C++ solution, we make use of a stack to store the characters of the result string. We use vectors to keep track of character frequencies and presence in the stack. Characters are pushed onto or popped from the stack based on the conditions provided.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in technical interviews at large tech companies. It tests understanding of greedy algorithms, stacks, and string manipulation, which are common interview topics.
A stack is the most suitable data structure because it helps maintain lexicographic ordering while allowing removal of previously added characters when a smaller valid character appears. A set or boolean array is also used to track whether a character is already included.
The optimal approach uses a greedy strategy combined with a monotonic stack. By tracking the last occurrence of each character and maintaining a stack of chosen characters, we ensure the result is lexicographically smallest while containing each character only once.
Tracking the last occurrence lets us know if a character removed from the stack will appear again later. This ensures we can safely pop a character to maintain lexicographic order without permanently losing it from the final result.
This Java solution repeatedly reevaluates whether to add each element into the result string itself, improving space performance vis-à-vis comparative approach and efficiency via, minimal edits required powers practical solution implementation.