# #5 Best Digits

###### tags:`Stack` `Medium`

## Problem
Write a function that takes a positive integer represented as a string `number` and an integer `numDigits`. Remove `numDigits` from the string so that the number represented by the string is as large as possible afterwards.
Note that the order of the remaining digits cannot be changed. You can assume `numDigits` will always be less than the length of `number` and greater than or equal to 0.

### Sample Input

number = "462839"
numDigits = 2

### Sample Output

"6839" // remove digits 4 and 2

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(n) space - where n is the length of the input string

:::

<br>

:::spoiler Hint 1
If we want the number to be as large as possible then which digits would we want to remove? Consider the importance of place values. For example if we're given `number = "191"` and `numDigits = 1` then which 1 would we remove?
:::

<br>

:::spoiler Hint 2
It's most important that the largest place values have the highest value digits. If you traverse the string from left to right then you will be traversing the place values in order of importance. If you still have digits to remove then you need to remove smaller digits in higher place values. The question then becomes how can you know what comes later on in the string? If you want to solve this problem in linear time what data structure might help you in this situation?
:::

<br>

:::spoiler Hint 3
Use a stack to push digits onto while traversing the string from left to right. That way top of the stack will always have the digit in the last highest place value. Compare the top of the stack to the current digit and if the current digit is greater than the top of the stack, then pop from the stack. Utilizing a stack allows you to replace small digits with largest digits that come later in the string because you can pop off of the stack in order of importance. You will need to build a string to return from the final stack.
:::

<br>

<hr/>

## Solutions

### Official

// O(n) time | O(n) space - where n is the length of the input string
function bestDigits(number, numDigits) {
  const stack = [];
  for (const digit of number) {
    while (numDigits > 0 && stack.length > 0 && digit > stack[stack.length - 1]) {
      numDigits--;
      stack.pop();
    }
    stack.push(digit)
  }
  while (numDigits > 0) {
    numDigits--;
    stack.pop();
  }
  return stack.join("");
}

<br>

---

### Everyone's

:::spoiler Sol

function bestDigits(number, numDigits) {
  // O(n) time O(n) space - where n is the length of the input string
  const stack = [];
  for (let n of number) {
    while (stack.length > 0 && numDigits > 0 && n > stack[stack.length-1]) {
      numDigits--;
      stack.pop();
    }
    stack.push(n)
  }
  if(numDigits > 0){
    for (let i = 0; i < numDigits; i++) {
      stack.pop();
    }
  }
  
  return stack.join('');
}

:::

<br>

:::spoiler 東

// Time O(m + n) | Space O(m) - m is length of input number string, n is input numDigits
function bestDigits(number, numDigits) {
  const stack = [number[0]];
  let removalNum = numDigits;
  for(let i = 1; i < number.length; i++){
    while(stack.length && +stack[stack.length - 1] < +number[i] && removalNum){
      stack.pop();
      removalNum--;
    }
    stack.push(number[i]);
  }

  if(removalNum > 0){
    stack.splice(stack.length - removalNum, removalNum);
  }
  
  return stack.reduce((acc, cur) => acc + cur, "");
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(n) where n is number.length;
 * Space complexity: O(n) where n is number.length;
 */

function bestDigits(number, numDigits) {
  const stack = [];

  for (const digit of number) {
    while (
      numDigits > 0 &&
      stack.length > 0 &&
      digit > stack[stack.length - 1]
    ) {
      numDigits -= 1;
      stack.pop();
    }

    stack.push(digit);
  }

  while (numDigits > 0) {
    numDigits -= 1;
    stack.pop();
  }

  return stack.join("");
}

:::

<br>

:::spoiler YC

/*
  time: O(n) - where n is the length of the number
  space: O(n) - where n is the length of the number
 * */
function bestDigits(number, numDigits) {
  const stack = [];
  for(const digit of number){
    while(stack.length && digit > stack[stack.length - 1] && numDigits){
      stack.pop();
      numDigits--;
    }
    stack.push(digit);
  }

  while(numDigits--){
    stack.pop();
  }
  
  return stack.join('');
}

:::

<br>

---

## Supplement / Discussion