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.
Input: s = "bcabc"
Output: "abc"
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
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
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
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
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
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
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
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
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
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