Erase Digits for the Smallest Number

Medium

A non-negative integer is written as the string number. Strike out exactly k of its digits (the rest keep their order) so that the resulting number is as small as possible. Return that number as a string without leading zeros. If no digits are left, or only zeros are, return "0".

Example 1

number="5291", k=2 → '21'

Strike out 5 and 9 to get 21; nothing smaller is possible.

Example 2

number="30045", k=1 → '45'

Remove the 3 to get "0045", which is "45" without the leading zeros.

Example 3

number="7", k=1 → '0'

All digits are gone, which counts as 0.

Constraints

1 ≤ k ≤ len(number) ≤ 10⁵
number consists of digits only
number has no leading zeros unless it is 0 itself

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy String Monotonic Stack

Similar problems

Every Letter Once Medium One Bead of Each Color Medium Smallest Pick With a Required Letter Hard Smallest Up-Down Sequence Medium Fix the Middle of the Line Medium

Input

number="5291", k=2

Expected

'21'

Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.