Smallest number after removing digits
Remove exactly k digits from a number written as text to leave the smallest possible number, by dropping a digit whenever the next digit is smaller. About 20 minutes.
Earlier places count more
You write a number as text and must delete exactly k digits so that the remaining number is as small as possible. Compare 1432 and 1423: they differ first at the third digit, so that digit decides.
The place of a digit matters more than later ones. So look for the first spot where a digit is bigger than the one after it, and delete that bigger digit. This lowers the number at the earliest possible place.
A stack does it in one pass
Walk through the digits with a stack of kept digits. For each new digit, while the top of the stack is larger and you still have removals left, pop it. Then push the new digit.
If removals remain at the end, the digits are in rising order, so drop them from the right end. Finally strip leading zeros, and if nothing is left the answer is 0.
stack = [1, 4] stack.pop() # 4 > the next digit k -= 1
Stack 3, then 5. Next the digit 1 is smaller than 5: pop 5 (k becomes 1).
Digits 1, 2, 3 with k = 1. What is left?
- A12
- B13
- C23
Show the answer
12. The digits already rise, so the leftover removal comes off the end.
Smallest number after removing k digits
Given a string num of digits and an integer k, remove exactly k digits so that the remaining number is as small as possible. Return it as a string without leading zeros. If nothing is left, return "0".
num = "1432219", k = 3 → "1219"
1 ≤ num.length ≤ 100,000 · 0 ≤ k ≤ num.length · num has no leading zeros