Coding Challenge Practice - Question 120

# algorithms# computerscience# devchallenge# javascript

Bukunmi Odugbesan

The task is to write a function to remove duplicate characters in a string function...

The task is to write a function to remove duplicate characters in a string

function smallestUniqueSubstr(str) {
  // your code here
}

Count the remaining occurrences of each character. This stores how many times each character appears

const remaining = {};
for(const ch of str) {
remaining[ch] = (remaining[ch] || 0) + 1;
}

Create data structures to build the final result and ensure uniqueness

const stack = []
const inStack = new Set()

Iterate through the string. Decrease the count as the character is being processed

for(const ch of str) {
remaining[ch]--

Skip the character if it has already been added to the result

if(inStack.has(ch)) return;

Remove characters from the stack if the stack is not empty, the current character is smaller top character, and the top character is greater than zero

while(
  stack.length > 0 &&
  stack[stack.length - 1] > ch &&
  remaining[stack[stack.length -1]] > 0
) {
  inStack.delete(stack.pop());
}

Add the current character to the result if all conditions are not met

stack.push(ch);
inStack.add(ch);

Return the final result

return stack.join('')

The final solution

function smallestUniqueSubstr(str) {
  // your code here
  const remaining = {};
  for(const ch of str) {
    remaining[ch] = (remaining[ch] || 0) + 1
  }

  const inStack = new Set();
  const stack = [];

  for(const ch of str) {
    remaining[ch]--;

    if(inStack.has(ch)) continue;

    while(stack.length > 0 && stack[stack.length - 1] > ch && 
    remaining[stack[stack.length -1]] > 0) {
      inStack.delete(stack.pop());
    }
    stack.push(ch);
    inStack.add(ch);
  }
  return stack.join('')
}

That's all folks!