Skills101
← All coding problems

Remove K Digits

mediumLinked List & Stack II+20 XPTime limit 2s

A shop's price tag shows a big number num. You may erase exactly k digits from it (the other digits keep their order). What is the smallest number you can leave? Leading zeros are dropped from the answer, and if nothing (or only zeros) is left, the answer is 0.

Input:

  • line 1: num — a non-negative integer without leading zeros (or just 0)
  • line 2: k

Output: the smallest possible number.

Constraints: 1 ≤ length of num ≤ 10⁵, 0 ≤ k ≤ length of num.

Think about it: a digit should go if the digit after it is smaller — removing it makes the number smaller in a more important place. Use a monotonic stack: while you still may remove digits and the top of the stack is larger than the new digit, pop it. If removals are left at the end, cut them from the tail.

Sample input 1

1432219
3

Sample output 1

1219

Sample input 2

10200
1

Sample output 2

200

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.