# Remove K Digits

Posted: 12 Apr, 2021

Difficulty: Moderate

#### You are given a non-negative integer ‘NUM’ in the form of a string and provided with an integer ‘K’. You need to find out the smallest integer possible by removing exactly ‘K’ digits from ‘NUM.’

##### Note :

```
‘NUM’ does not have leading zeros except when ‘NUM’ is equal to zero.
```

##### Input Format :

```
The first line contains an integer, ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a string ‘NUM’ and integer ‘K.’
```

##### Output Format :

```
For each test case, print a single string, the minimum integer that can be possibly made by removing ‘K’ digits from ‘NUM’.
Output for each test case will be printed in a separate line.
```

##### Note :

```
You don’t have to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <=10
2 <= |NUM| <= 10^5
0 <= K <= |NUM|
Where |NUM| denotes the length of the initial string ‘NUM’ and ‘K’ denotes the number of digits to be removed.
Time limit: 1 second
```

Approach 1

- This is the brute force solution, hence we will use recursion to compute the required integer of size ‘N’ - ‘K’.
- For each digit in the initial string “NUM” we have 2 options, either it is present in the current answer or it is not. Hence we can create a function
**findAll()**which takes the following parameters:- The initial string ‘NUM’.
- The current index ‘IDX’ which we either choose or not.
- String ‘CUR’ the answer from index 0 to ‘IDX’
- A variable ‘REMAIN’ which denotes how many digits are remaining to be added in the answer.

- Initially, ‘IDX’ is equal to 0 and goes till ‘N’, ‘REMAIN’ is equal to ‘N’ - ‘K’ and ‘CUR’ is empty.
- Whenever we choose a digit to include in the answer ‘REMAIN’ decreases by 1 and we move to the next ‘IDX’(i.e ‘IDX’ + 1). When ‘REMAIN’ is equal to 0 that means we have selected ‘N’ - ‘K’ digits and hence can compare if the current answer is minimum amongst all of the possible answers or not.

Approach 2

- This is a greedy algorithm. Suppose we have the initial string ‘NUM’ as “9122” where ‘K’ is 1. As ‘K’ is 1, our answer’s length will be equal to 4 - 1 = 3.
- Look into all possible answers.
- For the first digit we can choose ‘9’ as we have 3 digits after ‘9’ from which 2 digits can be chosen for the other subsequent characters in the answer.
- For the first digit we can also choose ‘1’ as there are 2 digits after ‘1’ out of which we can choose both and frame an answer of length 3.
- We cannot choose ‘2’(index 2) as there aren’t enough digits after index 2 frame an answer of length 3.
- Similarly we also cannot choose the last ‘2’ as the first digit of a possible answer.

- Therefore for the first digit the range of possible characters is in [0, ‘N’ - ‘K’) of the number ‘NUM’. We need to choose the smallest digit in this range. For duplicates, we choose the leftmost digit, i.e the digit with the lowest index.
- Let the index of the first digit be ‘FST’, then the range of the second digit is [‘FST’, ‘N’ - ‘K’ + 1).
- Repeat the above process to get all the ‘N’ - ‘K’ digits.

Approach 3

- We can just build a
**non-decreasing**string(if possible) using at max ‘K’ deletions and after building that remove some of the last characters from this**non-decreasing**string to get a valid optimum answer. - The reason why we build a non-decreasing string is that suppose we are allowed to make one deletion i.e
**‘K’**is at least 1, in that case instead of something like “42..” we would want the string to be something like “42..” i.e starting with a smaller character is always better. - Similarly, In we repeat the above process to get a non-decreasing string by doing at max
**‘K’**deletions. - In the end, if we still have some number of deletions left then we remove some of the last characters from the string we built till
**‘K’**becomes 0. - The resulting string is the answer.

SIMILAR PROBLEMS

# Ninja And Alternating Largest

Posted: 14 Jun, 2021

Difficulty: Easy

# Smallest divisor

Posted: 15 Jun, 2021

Difficulty: Moderate

# Break The Prison

Posted: 17 Jun, 2021

Difficulty: Moderate

# PostFix To Prefix

Posted: 24 Jun, 2021

Difficulty: Easy

# Queue using Array or Singly Linked List.

Posted: 27 Jul, 2021

Difficulty: Easy