Submission link - https://bigfrontend.dev/problem/remove-duplicate-letters-in-a-string/discuss/190
/**
* @param {string} str
* @return {string}
*/
function smallestUniqueSubstr(str) {
const chars = [...str]; // convert string to array of characters
const used = {}; // hold boolean value of if we iterated a char. Example: {a: true, b: false}
const result = []; // final string 😎
function storeCharsFrequency(acc, char) {
if (!acc[char]) { // if we don't have char in object then add it with frequency 1
acc[char] = 1;
} else {
acc[char]++; // if it already exist then increment value by 1
}
return acc; // return the object. Example: {a: 2, b: 1}
}
const hashMap = chars.reduce(storeCharsFrequency, {}); // for 'cbacba' it will be {"c": 2, "b": 2, "a": 2}
for (let i = 0; i < chars.length; i++) { // see 'Explanation' section
const char = chars[i];
hashMap[char]--;
if (used[char]) continue; // don't move ahead, iterate next element
// conditions: if char < last element of result AND last element's of result has one or more occurrences in the string
while (char < result[result.length - 1] && hashMap[result[result.length - 1]] > 0) {
used[result[result.length - 1]] = false; // mark the used for last element of result as false (because we are removing it in next line)
result.pop(); // remove it
}
result.push(char); // if all good then add current char
used[char] = true; // mark the current char as used so that we can prevent going in while condition when we encounter used trued for that char
}
return result.join(''); // it's time for beers! 🍻
}/**
* @param {string} str
* @return {string}
*/
function smallestUniqueSubstr(str) {
let result = ''; // final string 😎
const used = new Map(); // // hold boolean value of if we iterated a char. Example: {"a" => true, "b" => false}
function storeCharsFrequency(acc, char) {
if (!acc[char]) { // if we don't have char in object then add it with frequency 1
acc[char] = 1;
} else {
acc[char]++; // if it already exist then increment value by 1
}
return acc; // return the object. Example: {a: 2, b: 1}
}
const count = [...str].reduce(storeCharsFrequency, {}); // for 'cbacba' it will be {"c": 2, "b": 2, "a": 2}
for (let i = 0; i < str.length; i++) {
const char = str.charAt(i);
count[char]--;
if (used.get(char)) continue; // don't move ahead, iterate next element
// conditions: if char < last char of result string AND last element's of result has one or more occurrences in the string
while (char < result[result.length - 1] && count[result[result.length - 1]] > 0) {
used.set(result[result.length - 1], false); // mark the used for last char of result as false (because we are removing it in next line)
result = result.slice(0, -1); // remove last char of the result string
}
result = result + char; // if all good then add current char at the end of result string
used.set(char, true); // mark the current char as used so that we can prevent going in while condition when we encounter used trued for that char
}
return result; // it's time for beers! 🍻
}I thought I'm solving a duplicate string problem then I encountered a "lexicographical" word. 😁 I didn't have any clue what is lexicographical order. So before solving the problem I started reading it. It took a while to understand the term and its meaning in this problem's context.
I wrote my own algorithm (it was a disaster) but I was happy because I solved the 'Hard' Leetcode problem (https://leetcode.com/problems/remove-duplicate-letters/) In the beginning, I made an excuse and wanted to quit this problem because I thought it is hard.
I didn't give up and started reading how other people solved it. Finally, I got the gist of the algorithm and completed this problem.
We want to add a char 'C' if it is smaller than the last character 'L' of the result array but 'L' should have an occurrence after 'C'. If this condition is true then we simply remove 'L' from result array 'R' and mark used as false for 'L'. We will do it until this condition is satisfied.
Finally, we will push 'C' in 'R' and mark used as true for 'C'.
When in future iteration we counter the same 'C' then we simply ignore it and iterate the next char.
Example - 'cbacba' ==> 'abc'
hashMap = {"c": 2, "b": 2, "a": 2}
used = {"c": undefined, "b": undefined, "a": undefined}
[FIRST ITERATION] for loop on cbacba
- Reduce hashMap count for 'c' (it will become 2 to 1)
- Did we use it? No. As it is the first iteration and we never encountered it before.
- While loop - Is it smaller than the last char in the result? No. First iteration. Does it have a frequency greater than 0? Yes. But the first condition is false so we will come out of while loop
- Push "c" in the result array
- Mark "c" as used
[SECOND ITERATION] for loop on 'cbacba'
- Reduce hashMap count for 'b' (it will become 2 to 1)
- Did we use it? No. and we never encountered it before
- While loop - Is it smaller than the last char in the result? Yes. Does it have a frequency greater than 0? Yes. 3.1 Remove 'c' from result array and mark its used status false. As we removed it so as good as we didn't use it. Get out of the loop as there is char where 'b' is smaller
- push "b" in the result array
- Mark "b" as used
for loop .... till the length of the array.
-
Create a hash map (simple object) in JS to hold frequency of characters Example: string:
cbacba==> hashMap:{"c": 2, "b": 2, "a": 2} -
Create another object which has information about whether we used that char or not. Example: string:
cbacba==> used:{"a": true, "b": false, "c": false}. Intially they areundefined. Doesn't matterundefinedorfalseas they will act the same in if statement -
Loop over characters - Explained above in Algorithm part
- https://youtu.be/zhU7yshJvb0
- https://leetcode.com/problems/remove-duplicate-letters/discuss/?currentPage=1&orderBy=hot&query=
Say 'Hi' in your language to me on Twitter (@knowkalpesh)