Remove Duplicate Letters solution and explanation
Google
9 more videos on this problem
Remove Duplicate Letters | Leetcode #316Techdose · 14:55 · 37K views
Remove Duplicate Letters | Why Monotonic Stack | Intuition | Leetcode - 316 | Same as Leetcode 1081codestorywithMIK · 23:04 · 29K views
remove duplicate letters | leetcode 316 | smallest subsequence of distinct characters| leetcode 1081Naresh Gupta · 9:25 · 29K views
Remove Duplicate Letters | Leetcode 316 | Stack | Day-18Ayushi Sharma · 21:00 · 14K views
316. Remove Duplicate Letters | Day 015 | StackAryan Mittal · 13:36 · 12K views
Remove Duplicate Letters | LeetCode 316 & 1081 | October LeetCode Challenge | Day 11Learn Code Repeat · 16:47 · 8K views
Remove Duplicate Letters | Leet code 316 | Theory explained + Python codeSai Anish Malla · 17:32 · 6K views
Leetcode - Remove Duplicate Letters (Python)Timothy H Chang · 6:31 · 5K views
REMOVE DUPLICATE LETTERS | LEETCODE 316 | PYTHON STACK SOLUTIONCracking FAANG · 18:15 · 5K views
Remove Duplicate Letters | Leetcode 316 | Stacks | Live coding session 🔥🔥Coding Decoded · 14:46 · 3K views
The problem
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 <= 104sconsists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Approach overview
Problem Overview: Given a string s, remove duplicate characters so every letter appears exactly once while keeping the result as the smallest possible lexicographical string. The relative ordering constraints of the original string still matter, so you cannot freely reorder characters.
Approach 1: Greedy and Stack (O(n) time, O(1) space)
This approach uses a stack to build the result while maintaining lexicographical order. First record the last occurrence index of every character. Then iterate through the string and maintain a visited set. For each character, pop elements from the stack while the current character is smaller than the stack top and the stack top appears later in the string. This greedy decision ensures the final string remains lexicographically minimal. The stack effectively becomes a monotonic stack that enforces increasing order when possible.
Approach 2: Iterative Result String Construction (O(n) time, O(1) space)
This method builds the answer string directly instead of using an explicit stack structure. Iterate through characters and maintain a result string along with a visited map. When a new character arrives, repeatedly remove the last character from the result if it is lexicographically larger and appears again later in the string. Then append the current character and mark it as used. This follows the same greedy principle as the stack approach but uses string operations instead of a dedicated stack data structure. The algorithm still scans the input once and uses constant extra memory for character tracking.
Recommended for interviews: The greedy stack solution is the expected answer. Interviewers want to see that you track the last occurrence of each character and maintain a lexicographically minimal structure while iterating once through the string. Understanding how the greedy decision interacts with stack popping demonstrates strong algorithmic reasoning. The iterative string version shows the same logic but the explicit stack version is easier to explain during interviews.
Approach 1: Approach 1: Greedy and Stack
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.
def removeDuplicateLetters(s: str) -> str:
from collections import Counter
freq = Counter(s)
stack = []
in_stack = set()
for char in s:
freq[char] -= 1
if char in in_stack:
continue
while stack and stack[-1] > char and freq[stack[-1]] > 0:
in_stack.remove(stack.pop())
stack.append(char)
in_stack.add(char)
return ''.join(stack)
print(removeDuplicateLetters("cbacdcbc"))import java.util.Stack;
public class Solution {
public String removeDuplicateLetters(String s) {
int[] freq = new int[26];
boolean[] inStack = new boolean[26];
for (char c : s.toCharArray()) freq[c - 'a']++;
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
freq[c - 'a']--;
if (inStack[c - 'a']) continue;
while (!stack.isEmpty() && stack.peek() > c && freq[stack.peek() - 'a'] > 0) {
inStack[stack.pop() - 'a'] = false;
}
stack.push(c);
inStack[c - 'a'] = true;
}
StringBuilder res = new StringBuilder();
for (char c : stack) res.append(c);
return res.toString();
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.removeDuplicateLetters("cbacdcbc"));
}
}#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
string removeDuplicateLetters(string s) {
vector<int> freq(26, 0);
vector<bool> inStack(26, false);
for (char c : s) freq[c - 'a']++;
stack<char> result;
for (char c : s) {
freq[c - 'a']--;
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;
}function removeDuplicateLetters(s) {
const freq = new Array(26).fill(0);
const inStack = new Array(26).fill(false);
for (let char of s) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
const stack = [];
for (let char of s) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
if (inStack[char.charCodeAt(0) - 'a'.charCodeAt(0)]) continue;
while (stack.length > 0 && stack[stack.length - 1] > char && freq[stack[stack.length - 1].charCodeAt(0) - 'a'.charCodeAt(0)] > 0) {
inStack[stack.pop().charCodeAt(0) - 'a'.charCodeAt(0)] = false;
}
stack.push(char);
inStack[char.charCodeAt(0) - 'a'.charCodeAt(0)] = true;
}
return stack.join('');
}
console.log(removeDuplicateLetters("cbacdcbc"));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
char* removeDuplicateLetters(char* s) {
int n = strlen(s);
int freq[26] = {0};
bool inStack[26] = {false};
for (int i = 0; i < n; i++) freq[s[i] - 'a']++;
char* stack = (char*)malloc((n + 1) * sizeof(char));
int top = -1;
for (int i = 0; i < n; i++) {
freq[s[i] - 'a']--;
if (inStack[s[i] - 'a']) continue;
while (top >= 0 && stack[top] > s[i] && freq[stack[top] - 'a'] > 0) {
inStack[stack[top] - 'a'] = false;
top--;
}
stack[++top] = s[i];
inStack[s[i] - 'a'] = true;
}
stack[++top] = '\0';
return stack;
}
int main() {
char s[] = "cbacdcbc";
printf("%s\n", removeDuplicateLetters(s));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public string RemoveDuplicateLetters(string s) {
int[] freq = new int[26];
bool[] inStack = new bool[26];
foreach (char c in s) freq[c - 'a']++;
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
freq[c - 'a']--;
if (inStack[c - 'a']) continue;
while (stack.Count > 0 && stack.Peek() > c && freq[stack.Peek() - 'a'] > 0) {
inStack[stack.Pop() - 'a'] = false;
}
stack.Push(c);
inStack[c - 'a'] = true;
}
char[] result = stack.ToArray();
Array.Reverse(result);
return new string(result);
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.RemoveDuplicateLetters("cbacdcbc"));
}
}The Python implementation uses a stack to keep track of the correct order and a set to check if a character is already in the stack. The Counter from the collections module helps in efficiently counting character frequencies.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) as the maximum number of unique characters in a stack is 26.
Approach 2: Approach 2: Iterative with Result String Construction
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.
def removeDuplicateLetters(s: str) -> str:
freq = {char: s.count(char) for char in set(s)}
result = []
used = set()
for char in s:
freq[char] -= 1
if char in used:
continue
while result and result[-1] > char and freq[result[-1]] > 0:
used.remove(result.pop())
result.append(char)
used.add(char)
return ''.join(result)
print(removeDuplicateLetters("cbacdcbc"))public class Solution {
public String removeDuplicateLetters(String s) {
int[] freq = new int[26];
boolean[] used = new boolean[26];
for (char c : s.toCharArray()) freq[c - 'a']++;
StringBuilder res = new StringBuilder();
for (char c : s.toCharArray()) {
freq[c - 'a']--;
if (used[c - 'a']) continue;
while (res.length() > 0 && res.charAt(res.length() - 1) > c && freq[res.charAt(res.length() - 1) - 'a'] > 0) {
used[res.charAt(res.length() - 1) - 'a'] = false;
res.deleteCharAt(res.length() - 1);
}
res.append(c);
used[c - 'a'] = true;
}
return res.toString();
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.removeDuplicateLetters("cbacdcbc"));
}
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
string removeDuplicateLetters(const string& s) {
vector<int> freq(26, 0);
vector<bool> used(26, false);
for (char c : s) freq[c - 'a']++;
string res;
for (char c : s) {
freq[c - 'a']--;
if (used[c - 'a']) continue;
while (!res.empty() && res.back() > c && freq[res.back() - 'a'] > 0) {
used[res.back() - 'a'] = false;
res.pop_back();
}
res += c;
used[c - 'a'] = true;
}
return res;
}
int main() {
string s = "cbacdcbc";
cout << removeDuplicateLetters(s) << endl;
return 0;
}function removeDuplicateLetters(s) {
const freq = Array(26).fill(0);
const used = Array(26).fill(false);
for (const char of s) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
const result = [];
for (const char of s) {
const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
freq[index]--;
if (used[index]) continue;
while (result.length && result[result.length - 1] > char && freq[result[result.length - 1].charCodeAt(0) - 'a'.charCodeAt(0)]) {
used[result.pop().charCodeAt(0) - 'a'.charCodeAt(0)] = false;
}
result.push(char);
used[index] = true;
}
return result.join('');
}
console.log(removeDuplicateLetters("cbacdcbc"));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
char* removeDuplicateLetters(char* s) {
int len = strlen(s);
int freq[26] = {0};
bool used[26] = {false};
for (int i = 0; i < len; i++) freq[s[i] - 'a']++;
int pos = 0;
char* result = (char*)malloc((26 + 1) * sizeof(char));
for (int i = 0; i < len; i++) {
freq[s[i] - 'a']--;
if (!used[s[i] - 'a']) {
while (pos > 0 && result[pos - 1] > s[i] && freq[result[pos - 1] - 'a'] > 0) {
used[result[--pos] - 'a'] = false;
}
result[pos++] = s[i];
used[s[i] - 'a'] = true;
}
}
result[pos] = '\0';
return result;
}
int main() {
char s[] = "cbacdcbc";
printf("%s\n", removeDuplicateLetters(s));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public string RemoveDuplicateLetters(string s) {
int[] freq = new int[26];
bool[] used = new bool[26];
foreach (char c in s) freq[c - 'a']++;
Stack<char> result = new Stack<char>();
foreach (char c in s) {
freq[c - 'a']--;
if (used[c - 'a']) continue;
while (result.Count > 0 && result.Peek() > c && freq[result.Peek() - 'a'] > 0) {
used[result.Pop() - 'a'] = false;
}
result.Push(c);
used[c - 'a'] = true;
}
char[] res = result.ToArray();
Array.Reverse(res);
return new string(res);
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.RemoveDuplicateLetters("cbacdcbc"));
}
}This Python code offers a readable solution that retains the resulting direct string construction while handling conditionals effectively. It uses array substitution optimizing continuous consistent checks engaging further space efficiency benefits achieved.
Time Complexity: O(n), with n articulating progression sequential handling entire input string.
Space Complexity: O(1), determined constant through compact storage non-collateral deployment.
Approach 3: Stack
We use an array last to record the last occurrence of each character, a stack to save the result string, and an array vis or an integer variable mask to record whether the current character is in the stack.
Traverse the string s, for each character c, if c is not in the stack, we need to check whether the top element of the stack is greater than c. If it is greater than c and the top element of the stack will appear later, we pop the top element of the stack and push c into the stack.
Finally, concatenate the elements in the stack into a string and return it as the result.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
func removeDuplicateLetters(s string) string {
last := make([]int, 26)
for i, c := range s {
last[c-'a'] = i
}
stk := []rune{}
vis := make([]bool, 128)
for i, c := range s {
if vis[c] {
continue
}
for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
vis[stk[len(stk)-1]] = false
stk = stk[:len(stk)-1]
}
stk = append(stk, c)
vis[c] = true
}
return string(stk)
}Approach 4: Default Approach
func removeDuplicateLetters(s string) string {
count, in_stack, stack := make([]int, 128), make([]bool, 128), make([]rune, 0)
for _, c := range s {
count[c] += 1
}
for _, c := range s {
count[c] -= 1
if in_stack[c] {
continue
}
for len(stack) > 0 && stack[len(stack)-1] > c && count[stack[len(stack)-1]] > 0 {
peek := stack[len(stack)-1]
stack = stack[0 : len(stack)-1]
in_stack[peek] = false
}
stack = append(stack, c)
in_stack[c] = true
}
return string(stack)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy and Stack | Time Complexity: O(n), where n is the length of the string. |
| Approach 2: Iterative with Result String Construction | Time Complexity: O(n), with n articulating progression sequential handling entire input string. |
| Stack | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy + Monotonic Stack | O(n) | O(1) | Best general solution. Clear logic for maintaining smallest lexicographic order while ensuring each character appears once. |
| Iterative Result String Construction | O(n) | O(1) | Useful when implementing without an explicit stack structure while applying the same greedy removal logic. |
Frequently asked questions
Is Remove Duplicate Letters easy or hard?
Remove Duplicate Letters is typically classified as a medium-level problem. The implementation is not long, but identifying the greedy rule and safely popping characters from a stack requires careful reasoning about future occurrences in the string.
Remove Duplicate Letters Python/Java solution
In Python or Java, implement the greedy stack approach using a list or stack structure along with arrays to track last occurrences and visited characters. Iterate through the string once, pop larger characters that appear later, and append the current character if it hasn't been used yet.
How to solve Remove Duplicate Letters in O(n)?
Record the last index of each character in the string. Iterate through the string and maintain a stack and a visited set. While the stack is not empty and the current character is smaller than the top of the stack and the top appears later again, pop it from the stack. Push the current character if it hasn't been used. This guarantees the lexicographically smallest valid string.
What is the best approach for Remove Duplicate Letters?
The greedy monotonic stack approach is the most efficient solution. Track the last occurrence of each character and iterate through the string once. Maintain a stack and remove larger characters that will appear again later, ensuring the resulting string stays lexicographically smallest. This runs in O(n) time with O(1) extra space.
Is Remove Duplicate Letters asked at Google/Amazon/Meta?
Remove Duplicate Letters frequently appears in interviews at companies like Amazon, Google, and Meta because it tests greedy reasoning and stack usage. Candidates must combine character frequency tracking with a monotonic structure, which is a common pattern in advanced string problems.
What data structure is used in Remove Duplicate Letters?
A stack is the primary data structure used in the optimal solution. The stack maintains the current lexicographically smallest sequence while allowing removal of previously added characters. A hash map or array tracks the last occurrence of each character, and a boolean array or set tracks visited characters.
What is the time complexity of Remove Duplicate Letters?
The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed to and popped from the stack at most once, so the total number of operations is linear. Space complexity is O(1) because the alphabet size is fixed (26 lowercase letters).