Remove Duplicate Letters
Remove Duplicate Letters is a medium monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (monotonic stack), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (greedy rebuild, one letter at a time) up.
Problem
You are given a string s of lowercase letters. Delete characters so that every distinct letter of s appears exactly once in what remains, keeping the remaining characters in their original order.
Among all strings you can get this way, return the one that is smallest in lexicographical (dictionary) order.
Examples
Example 1
- Input
s = "dcbacd"- Output
"bacd"- Why
- The kept letters must be one each of a, b, c, d. b has no copy after the a, so b must come before a; among the remaining choices "bacd" is the smallest.
Example 2
- Input
s = "zxyzxa"- Output
"xyza"- Why
- Dropping the first z lets x come first, and the later z still fits before the final a.
Example 3
- Input
s = "bbaacc"- Output
"bac"- Why
- Every b comes before every a, so the result cannot start with a.
Constraints
1 <= s.length <= 10^4sconsists of lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (greedy rebuild, one letter at a time) | O(k · n) | O(n) |
| Optimal (monotonic stack) | O(n) | O(1) |
1Brute force (greedy rebuild, one letter at a time)
O(k · n)Each of the k ≤ 26 output letters needs a pass over the remaining string.O(n)The shrinking copy of the string and the output.Decide the answer one letter at a time. For the next position, scan the remaining string and take the leftmost position of the smallest letter such that every still-needed letter appears at or after it. Append that letter, cut the string after that position, delete every copy of that letter from what remains, and repeat.
- rest = s.
- While rest is not empty: count the letters of rest.
- Walk rest from the left, decreasing counts; remember the smallest letter seen. Stop at the first index where some letter's count drops to 0. That smallest letter (first occurrence) is safe to place.
- Append it, set rest = the part after that occurrence with all copies of that letter removed.
class Solution {
public String removeDuplicateLetters(String s) {
StringBuilder result = new StringBuilder();
String rest = s;
while (!rest.isEmpty()) {
int[] count = new int[26];
for (int i = 0; i < rest.length(); i++) count[rest.charAt(i) - 'a']++;
int best = 0;
for (int i = 0; i < rest.length(); i++) {
if (rest.charAt(i) < rest.charAt(best)) best = i;
if (--count[rest.charAt(i) - 'a'] == 0) break;
}
char chosen = rest.charAt(best);
result.append(chosen);
rest = rest.substring(best + 1).replace(String.valueOf(chosen), "");
}
return result.toString();
}
}class Solution:
def removeDuplicateLetters(self, s: str) -> str:
result = []
rest = s
while rest:
count = [0] * 26
for ch in rest:
count[ord(ch) - ord('a')] += 1
best = 0
for i, ch in enumerate(rest):
if ch < rest[best]:
best = i
count[ord(ch) - ord('a')] -= 1
if count[ord(ch) - ord('a')] == 0:
break
chosen = rest[best]
result.append(chosen)
rest = rest[best + 1:].replace(chosen, "")
return "".join(result)class Solution {
public:
string removeDuplicateLetters(string s) {
string result;
string rest = s;
while (!rest.empty()) {
int count[26] = {0};
for (char ch : rest) count[ch - 'a']++;
int best = 0;
for (int i = 0; i < (int) rest.size(); i++) {
if (rest[i] < rest[best]) best = i;
if (--count[rest[i] - 'a'] == 0) break;
}
char chosen = rest[best];
result += chosen;
string next;
for (int i = best + 1; i < (int) rest.size(); i++) {
if (rest[i] != chosen) next += rest[i];
}
rest = next;
}
return result;
}
};function removeDuplicateLetters(s) {
let result = "";
let rest = s;
while (rest.length > 0) {
const count = new Array(26).fill(0);
for (let i = 0; i < rest.length; i++) count[rest.charCodeAt(i) - 97]++;
let best = 0;
for (let i = 0; i < rest.length; i++) {
if (rest[i] < rest[best]) best = i;
if (--count[rest.charCodeAt(i) - 97] === 0) break;
}
const chosen = rest[best];
result += chosen;
rest = rest.substring(best + 1).split(chosen).join("");
}
return result;
}2Optimal (monotonic stack)
O(n)Each letter is pushed and popped at most once.O(1)The stack holds at most 26 letters and the helper arrays have 26 entries.Record the last index of every letter. Scan the string once, keeping the answer so far on a stack. Skip a letter already on the stack. Otherwise, while the top of the stack is larger than the current letter and that top letter appears again later, pop it, because placing it later gives a smaller string. Then push the current letter.
- last[c] = last index of letter c; inStack[c] = false.
- For each index i with letter c: if inStack[c], continue.
- While the stack is not empty, top > c and last[top] > i: pop top and clear inStack[top].
- Push c and set inStack[c] = true.
- The stack from bottom to top is the answer.
class Solution {
public String removeDuplicateLetters(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
boolean[] inStack = new boolean[26];
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (inStack[c - 'a']) continue;
while (stack.length() > 0) {
char top = stack.charAt(stack.length() - 1);
if (top <= c || last[top - 'a'] < i) break;
stack.deleteCharAt(stack.length() - 1);
inStack[top - 'a'] = false;
}
stack.append(c);
inStack[c - 'a'] = true;
}
return stack.toString();
}
}class Solution:
def removeDuplicateLetters(self, s: str) -> str:
last = {ch: i for i, ch in enumerate(s)}
in_stack = set()
stack = []
for i, ch in enumerate(s):
if ch in in_stack:
continue
while stack and stack[-1] > ch and last[stack[-1]] > i:
in_stack.remove(stack.pop())
stack.append(ch)
in_stack.add(ch)
return "".join(stack)class Solution {
public:
string removeDuplicateLetters(string s) {
int last[26] = {0};
for (int i = 0; i < (int) s.size(); i++) last[s[i] - 'a'] = i;
bool inStack[26] = {false};
string stack;
for (int i = 0; i < (int) s.size(); i++) {
char c = s[i];
if (inStack[c - 'a']) continue;
while (!stack.empty() && stack.back() > c && last[stack.back() - 'a'] > i) {
inStack[stack.back() - 'a'] = false;
stack.pop_back();
}
stack.push_back(c);
inStack[c - 'a'] = true;
}
return stack;
}
};function removeDuplicateLetters(s) {
const last = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) last[s.charCodeAt(i) - 97] = i;
const inStack = new Array(26).fill(false);
const stack = [];
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (inStack[s.charCodeAt(i) - 97]) continue;
while (stack.length > 0 && stack[stack.length - 1] > c && last[stack[stack.length - 1].charCodeAt(0) - 97] > i) {
inStack[stack.pop().charCodeAt(0) - 97] = false;
}
stack.push(c);
inStack[s.charCodeAt(i) - 97] = true;
}
return stack.join("");
}Edge cases to test
- Every letter appears once: the string is returned unchanged
- All characters are the same letter: the answer has length 1
- Letters in strictly decreasing order with no repeats, so nothing can be moved
- A large letter that has no later copy must stay even though smaller letters follow it
Hints
Hint 1
The answer contains each distinct letter exactly once. Build it from left to right and always try to place the smallest letter possible.
Hint 2
A letter can be placed next only if everything still missing appears somewhere after its position.
Hint 3
Scan once with a stack. When the current letter is smaller than the top of the stack and the top letter occurs again later, pop it: a later copy can take its place.
FAQ
What is the best time complexity for Remove Duplicate Letters?
Optimal (monotonic stack) runs in O(n) time and O(1) extra space. Each letter is pushed and popped at most once.
Which pattern does Remove Duplicate Letters use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Remove Duplicate Letters?
Yes. Brute force (greedy rebuild, one letter at a time) takes O(k · n) time and O(n) space. Decide the answer one letter at a time.
Which edge cases should I test for Remove Duplicate Letters?
Every letter appears once: the string is returned unchanged; All characters are the same letter: the answer has length 1; Letters in strictly decreasing order with no repeats, so nothing can be moved; A large letter that has no later copy must stay even though smaller letters follow it.