Remove K Digits
Remove exactly k digits from a numeric string so the remaining number is the smallest possible.
Open on LeetCode ↗Intuition
The stack part of this problem is the easy half; nearly every wrong submission passes the pop logic and fails on the cleanup after. If the sweep never finds anything worth popping — the string is already non-decreasing, like "12345" — k removals still remain unspent, and they have to come off the end, where place value is lowest, not the front. Then the result can start with zeros the stack never stripped, and if k equals the string length the whole stack empties and returning an empty string is wrong. Sweep left to right with a stack, popping while the top exceeds the incoming digit and removals remain, and treat the cleanups as mandatory, not optional.
Approach
Find the highest-value removal
If digit d is immediately followed by a smaller digit, removing d promotes something smaller into a more significant position, which always lowers the number. Any digit followed by a larger one is better kept, since removing it would promote something bigger.
Enforce it with a monotonic stack
Push digits left to right. While the stack top is greater than the incoming digit and k > 0, pop and decrement k. Each pop is exactly the removal identified above, applied as early — and therefore as significantly — as possible.
Handle the leftovers
Three cleanups, and skipping any one fails a real test case. If k remains after the sweep, the string is non-decreasing, so remove from the end with st[:-k] — removing from the front is the mistake, since the front already passed through the pop logic. Strip leading zeros with lstrip('0'). If nothing survives, return "0" rather than an empty string. O(n) time, O(n) space.
Solution & live demo
Edge cases
Everything is removed, so return "0".
Strip them — the answer is "200", not "0200".
No pops fire, so the trailing removal path handles all of k.
Stripping empties the string, so the explicit "0" fallback is required.