Problem of the day
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.’
‘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.
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’.
123
1
12
We can remove the last digit, ‘3’ to get the smallest possible answer, ‘12’.
Other possible answers are ‘23’ and ‘13’, all of which are greater than ‘12’.
3214
2
14
In this case, six numbers can be formed: 32, 31, 34, 21, 24, 14.
Out of which 14 is the smallest.
The expected time complexity is O(n).
2 <= |num| <= 10^6
0 <= k <= |num|
Time limit: 1 second
Where |num| denotes the length of the initial string ‘num’ and ‘k’ represents the number of digits to be removed.
If we remove ‘k’ digits from the initial number of say, length ‘n’, then the length of our answer will be ‘n’ - ‘k'. Find all the integers you can create from ‘num’ of length ‘n’ - ‘k’ and output the minimum amongst them.
O(2^n), where ‘n’ is the length of the string ‘num.’
For every character in ‘num’, we have 2 options, either we include it in the current answer ‘cur’ or not. Hence, we have two options for each of the ‘n’ characters, making the total time complexity O(2^n).
O(n), where ‘n’ is the length of the string ‘num.’
We use recursion to find the optimal answer. For a recursive call stack, the space complexity is always proportional to the depth of the recursive call tree, which is equal to ‘n’. Hence space complexity is O(n).