Remove Duplicate Letters — Solution in Python, Java & C++
Remove Duplicate Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Duplicate Letters is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Stack, Monotonic Stack
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, remove duplicate letters so that every letter appears exactly once, and among all such results return the lexicographically smallest one.
Example 1
Input: s = "bcabc"
Output: abc
Example 2
Input: s = "cbacdcbc"
Output: acdb
Example 3
Input: s = "abc"
Output: abc
Constraints
1 <= s.length <= 40s consists of lowercase English letters.
Hints for Remove Duplicate Letters
Hint 1
Build the answer on a stack that you keep as small as possible, lexicographically.
Hint 2
Before pushing a character, pop any larger character on top — but only if that character occurs again later, so dropping it is safe.
Hint 3
Skip characters already on the stack; each letter must appear once.
How to solve Remove Duplicate Letters
Build the answer on a monotonic stack: before pushing a character, pop any larger top that still occurs later, and skip characters already on the stack.
Approach
- Record the last index of each character.
- For each
ch: skip if already on the stack; while the top is greater thanchand its last index is beyondi, pop it; pushch.
Why it works
Popping a larger character that reappears later never loses it and makes the prefix smaller; refusing to pop one that does not reappear preserves the every-letter-once guarantee. The stack is therefore the lexicographically smallest valid subsequence.
Complexity
- Time —
O(n) - Space —
O(26)
Pitfalls
- Forgetting the "occurs later" check drops letters permanently.
Reference solution
Python
def removeDuplicateLetters(s: str) -> str:
last = {ch: i for i, ch in enumerate(s)}
stack = []
in_stack = set()
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.discard(stack.pop())
stack.append(ch)
in_stack.add(ch)
return "".join(stack)Java
public static String removeDuplicateLetters(String s) {
int[] last = new int[26];
for (int i = 0; i < 26; i++) last[i] = -1;
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
StringBuilder stack = new StringBuilder();
boolean[] inStack = new boolean[26];
for (int i = 0; i < s.length(); i++) {
int c = s.charAt(i) - 'a';
if (inStack[c]) continue;
while (stack.length() > 0) {
int top = stack.charAt(stack.length() - 1) - 'a';
if (top > c && last[top] > i) {
inStack[top] = false;
stack.deleteCharAt(stack.length() - 1);
} else {
break;
}
}
stack.append(s.charAt(i));
inStack[c] = true;
}
return stack.toString();
}C++
string removeDuplicateLetters(string s) {
vector<int> last(26, -1);
for (int i = 0; i < (int) s.size(); i++) last[s[i] - 'a'] = i;
string stk;
vector<bool> inStack(26, false);
for (int i = 0; i < (int) s.size(); i++) {
int c = s[i] - 'a';
if (inStack[c]) continue;
while (!stk.empty()) {
int top = stk.back() - 'a';
if (top > c && last[top] > i) {
inStack[top] = false;
stk.pop_back();
} else {
break;
}
}
stk.push_back(s[i]);
inStack[c] = true;
}
return stk;
}JavaScript
var removeDuplicateLetters = function(s) {
const lastIndex = new Map();
for (let i = 0; i < s.length; i++) lastIndex.set(s[i], i);
const stack = [];
const inStack = new Set();
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (inStack.has(c)) continue;
while (stack.length > 0 && stack[stack.length - 1] > c && lastIndex.get(stack[stack.length - 1]) > i) {
inStack.delete(stack.pop());
}
stack.push(c);
inStack.add(c);
}
return stack.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms