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.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

Input: num = “1432219”, k = 3 Output: “1219” Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = “10200”, k = 1 Output: “200” Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = “10”, k = 2 Output: “0” Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Solution

Here we can use Stack to keep track of the visited characters, Start iterating number from left and push it to the Stack, We can get minimum number if current digit is smaller then the previous digit.

For Example, num = “1432219”, k = 1 Removing “4” will give the minimum number as “132219”.

Iterate above approach till k times.

Code

Output

1219

Complexity Analysis

Time complexity: O(N).
Space Complexity: O(N).

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *