Remove Duplicate Letters
On this page 
Problem Statement Solution 1: Greedy Approach with Stack Solution 2: Using a Greedy Approach with Count Arrays Solution 3: Using Last Occurrence Map and Stack Solution 4: Using Character Frequency and Stack Solution 5: Recursive Backtracking Approach Solution 6: Using a Linked List for Result Construction Solution 7: Using a Frequency Count Array Solution 8: Using a Stack with Priority Queue Solution 9: Using Sorting and Set for Deduplication Solution 10: Using Hash Maps and Sorting More Problems Solutions
Problem Statement
You are given a string s consisting of lowercase English letters. Your task is to remove duplicate letters from the string so that every letter appears exactly once, and the resulting string is the smallest lexicographically among all possible results. In other words, the final string should be the smallest possible in alphabetical order after removing duplicates.
Example 1
Input: s = "bcabc"
Output: "abc"
Solution 1: Greedy Approach with Stack
function removeDuplicateLettersStack(s) {
const stack = [];
const inStack = new Set();
const lastOccurrence = {};
for (const char of s) {
lastOccurrence[char] = s.lastIndexOf(char);
}
for (const char of s) {
if (inStack.has(char)) continue;
while (stack.length && char < stack[stack.length - 1] && lastOccurrence[stack[stack.length - 1]] > s.indexOf(char)) {
inStack.delete(stack.pop());
}
stack.push(char);
inStack.add(char);
}
return stack.join('');
}
const s1 = "bcabc";
removeDuplicateLettersStack(s1); //output: abc
Solution 2: Using a Greedy Approach with Count Arrays
function removeDuplicateLettersGreedy(s) {
const count = Array(26).fill(0);
const inResult = Array(26).fill(false);
for (const char of s) {
count[char.charCodeAt() - 'a'.charCodeAt()]++;
}
const result = [];
for (const char of s) {
count[char.charCodeAt() - 'a'.charCodeAt()]--;
if (inResult[char.charCodeAt() - 'a'.charCodeAt()]) continue;
while (result.length && char < result[result.length - 1] && count[result[result.length - 1].charCodeAt() - 'a'.charCodeAt()] > 0) {
inResult[result.pop().charCodeAt() - 'a'.charCodeAt()] = false;
}
result.push(char);
inResult[char.charCodeAt() - 'a'.charCodeAt()] = true;
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersGreedy(s1); //output: abc
Solution 3: Using Last Occurrence Map and Stack
function removeDuplicateLettersLastOccurrence(s) {
const lastIndex = {};
const stack = [];
const inStack = new Set();
for (let i = 0; i < s.length; i++) {
lastIndex[s[i]] = i;
}
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (inStack.has(char)) continue;
while (stack.length && char < stack[stack.length - 1] && i < lastIndex[stack[stack.length - 1]]) {
inStack.delete(stack.pop());
}
stack.push(char);
inStack.add(char);
}
return stack.join('');
}
const s1 = "bcabc";
removeDuplicateLettersLastOccurrence(s1); //output: abc
Solution 4: Using Character Frequency and Stack
function removeDuplicateLettersCharFrequency(s) {
const freq = Array(26).fill(0);
const inResult = Array(26).fill(false);
const result = [];
for (const char of s) {
freq[char.charCodeAt() - 'a'.charCodeAt()]++;
}
for (const char of s) {
const index = char.charCodeAt() - 'a'.charCodeAt();
freq[index]--;
if (inResult[index]) continue;
while (result.length && char < result[result.length - 1] && freq[result[result.length - 1].charCodeAt() - 'a'.charCodeAt()] > 0) {
inResult[result.pop().charCodeAt() - 'a'.charCodeAt()] = false;
}
result.push(char);
inResult[index] = true;
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersCharFrequency(s1); //output: abc
Solution 5: Recursive Backtracking Approach
function removeDuplicateLettersBacktrack(s) {
const lastIndex = {};
const result = [];
const used = Array(26).fill(false);
for (let i = 0; i < s.length; i++) {
lastIndex[s[i]] = i;
}
function backtrack(start) {
if (start === s.length) return result.join('');
for (let i = start; i < s.length; i++) {
const char = s[i];
if (used[char.charCodeAt() - 'a'.charCodeAt()]) continue;
while (result.length && char < result[result.length - 1] && lastIndex[result[result.length - 1]] > i) {
used[result.pop().charCodeAt() - 'a'.charCodeAt()] = false;
}
result.push(char);
used[char.charCodeAt() - 'a'.charCodeAt()] = true;
}
return result.join('');
}
return backtrack(0);
}
const s1 = "bcabc";
removeDuplicateLettersBacktrack(s1); //output: abc
Solution 6: Using a Linked List for Result Construction
function removeDuplicateLettersLinkedList(s) {
const lastOccurrence = {};
const result = [];
const inResult = new Set();
for (const char of s) {
lastOccurrence[char] = s.lastIndexOf(char);
}
for (const char of s) {
if (inResult.has(char)) continue;
while (result.length && char < result[result.length - 1] && lastOccurrence[result[result.length - 1]] > s.indexOf(char)) {
inResult.delete(result.pop());
}
result.push(char);
inResult.add(char);
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersLinkedList(s1); //output: abc
Solution 7: Using a Frequency Count Array
function removeDuplicateLettersFreqArray(s) {
const count = Array(26).fill(0);
const inResult = Array(26).fill(false);
const result = [];
for (const char of s) {
count[char.charCodeAt() - 'a'.charCodeAt()]++;
}
for (const char of s) {
const index = char.charCodeAt() - 'a'.charCodeAt();
count[index]--;
if (inResult[index]) continue;
while (result.length && char < result[result.length - 1] && count[result[result.length - 1].charCodeAt() - 'a'.charCodeAt()] > 0) {
inResult[result.pop().charCodeAt() - 'a'.charCodeAt()] = false;
}
result.push(char);
inResult[index] = true;
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersFreqArray(s1); //output: abc
Solution 8: Using a Stack with Priority Queue
function removeDuplicateLettersPriorityQueue(s) {
const lastOccurrence = {};
const result = [];
const inResult = new Set();
for (let i = 0; i < s.length; i++) {
lastOccurrence[s[i]] = i;
}
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (inResult.has(char)) continue;
while (result.length && char < result[result.length - 1] && lastOccurrence[result[result.length - 1]] > i) {
inResult.delete(result.pop());
}
result.push(char);
inResult.add(char);
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersPriorityQueue(s1); //output: abc
Solution 9: Using Sorting and Set for Deduplication
function removeDuplicateLettersSorting(s) {
const result = [];
const inResult = new Set();
const sortedChars = [...new Set(s)].sort();
for (const char of sortedChars) {
if (inResult.has(char)) continue;
while (result.length && char < result[result.length - 1] && s.indexOf(result[result.length - 1]) < s.indexOf(char)) {
inResult.delete(result.pop());
}
result.push(char);
inResult.add(char);
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersSorting(s1); //output: abc
Solution 10: Using Hash Maps and Sorting
function removeDuplicateLettersHashMap(s) {
const lastOccurrence = {};
const count = Array(26).fill(0);
const result = [];
const inResult = new Set();
for (let i = 0; i < s.length; i++) {
lastOccurrence[s[i]] = i;
count[s[i].charCodeAt() - 'a'.charCodeAt()]++;
}
for (let i = 0; i < s.length; i++) {
const char = s[i];
count[char.charCodeAt() - 'a'.charCodeAt()]--;
if (inResult.has(char)) continue;
while (result.length && char < result[result.length - 1] && lastOccurrence[result[result.length - 1]] > i) {
inResult.delete(result.pop());
}
result.push(char);
inResult.add(char);
}
return result.join('');
}
const s1 = "bcabc";
removeDuplicateLettersHashMap(s1); //output: abc