Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Observation 1: We need to select the first k digits which is most significant as least possible.

Consider this example "191" and k = 1

As we go throught "191"

- 91 -> min = 91, "1" is removed
- 11 -> min = 11, "9" is removed
- 19 -> min = 11, "1" is removed

Here 9 is the most significant digit which means, if any digit less than 9 will make the whole number lesser

In order to solve this kinnd of problem you can think of greedy algorithm

Greedy algorithm is a technique used whenever an optimal solution is required(i.e, min or max)

Here, we need the smallest number possible

Let's see the algorithm

- Create a stack to hold the numbers
- Loop through each element in the num string
- while
`stack length > 0 && k > 0 && stack[stack.length - 1] > num[i]`

- Pop the elements in the stack and decrease k by 1
- Push each elem to the stack
- After coming out of for loop, if
`k > 0`

pop k times from stack - Now remove any leading
`0`

's from the stack - Now convert the stack to string and return it
- There is a edge case when there is "0", it might return empty string, handle it

Let's consider few examples of different scenarios

**Case 1:**

num = "1432219" and k = 3

We need to find the best fit for the first 3 digits in num which is smallest possible. i.e, 143 should be replaced with smallest fit as they are most significant

Steps:

- stack = [1], k = 3
- stack = [1, 4], k = 3
- stack = [1, 4, 3], k = 3
- stack = [1, 4], k = 2 as 3 > 2
- stack = [1], k = 1 as 4 > 2
- stack = [1, 2], k = 1
- stack = [1, 2, 2], k = 1
- stack = [1, 2], k = 0 as 2 > 1
- stack = [1, 2, 1]
- stack = [1, 2, 1, 9]

Here's the code

```
var removeKdigits = function(num, k) {
let stack = new Array();
for(let i = 0; i < num.length; i++) {
while(stack.length > 0 && k > 0 && stack[stack.length - 1] > num[i]) {
stack.pop();
k--;
}
stack.push(num[i])
}
while(k > 0) {
stack.pop();
k--;
}
let res = stack.join('');
while(res.charAt(0) === '0') {
res = res.slice(1);
}
if(res.length == 0) {
return "0";
}
return res;
};
```

## Oldest comments (0)