Last Updated: 12 Apr, 2021
Remove K Digits
Moderate
Asked in companies
You are given a non-negative integer ‘num’ in the form of a string and provided with an integer ‘k’.
You need to find the smallest integer possible by removing exactly ‘k’ digits from ‘num.’
Note :
‘num’ does not have leading zeros except when ‘num’ equals zero.
Example:
Input: ‘num’ = ‘141’ , ‘k’ = 1.
Output: ‘11’
Explanation: By removing only 1 digit from ‘num’, 3 numbers can be formed: 14, 11, and 41. Out of which 11 is the smallest number.
Note :
You don’t have to print anything. It has already been taken care of. Just implement the given function.
Input Format :
The first line of the input contains the string 'num'.
The second line contains the integer 'k'.
Output Format :
For each test case, return a string, the minimum integer that can be made by removing ‘k’ digits from ‘num’.
Approaches
- 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’ denotes how many digits remain 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.
- 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 to 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.
- 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.