Remove K Digits
Problem
Given a non-negative integer as a string and a number k, delete exactly k digits so that the remaining number is as small as possible. Return it as a string without leading zeros, or "0" if nothing is left.
Examples
Constraints
- • 1 <= k <= num.length <= 10^5
- • num has no leading zeros except the number 0 itself
Hints & approach
Hint 1
The leftmost digits matter most for the size of the number.
Hint 2
If a digit is larger than the one after it, removing it helps.
Hint 3
A stack that stays non-decreasing captures this greedily.
Approachtry the hints first
Scan digits and keep a stack that stays non-decreasing. Before pushing digit d, while k > 0 and the top is greater than d, pop it and decrement k; this removes a larger digit sitting before a smaller one, which is always the best deletion. If k is still positive after the scan, drop that many digits from the end, since the stack is non-decreasing. Strip leading zeros and return "0" for an empty result.
Time O(n) · Space O(n)