Remove K Digits

Problem

You are given a string num representing a non-negative integer with no sign, and an integer k. Delete exactly k digits from num so that the remaining digits, read in their original order, form the smallest possible number. Return that number as a string without leading zeros; if every digit is removed, return "0".

• num has between 1 and 200,000 digits, and k is between 1 and the number of digits.
• num consists of digits only and has no leading zeros except when it is exactly "0".

Examples

• num = "5723841", k = 3 → "2341". Deleting 5, 7, and 8 leaves the smallest arrangement of four digits.
• num = "20500", k = 1 → "500". Removing the 2 leaves 0500, and leading zeros are stripped.
• num = "47", k = 2 → "0". Everything is removed.

Hints

1. Compare two numbers of equal length: what decides which is smaller?
2. If a digit is larger than the digit right after it, removing it makes the number smaller. Which such digit should you remove first?
3. Keep a stack of digits that is non-decreasing; while k > 0 and the incoming digit is smaller than the top, pop. Whatever k remains, trim from the end.