Remove K Digits

def remove_k_digits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop()           # launch it
            k -= 1
        stack.append(d)
    if k:                         # leftovers
        stack = stack[:-k]
    return "".join(stack).lstrip("0") or "0"

Remove K Digits. Given a number as a string and a count k, remove k digits to leave the smallest number possible. No leading zeros, and an empty result is zero.

One, four, three, two, two, one, nine, with k equal to three, becomes one, two, one, nine. One, zero, two, zero, zero, with k equal to one, drops the one, then the leading zero: two hundred. One, zero, with k equal to two, leaves nothing: zero.

The slow way tries every set of k digits to remove. That's n choose k choices, each built and compared.

The key idea is greedy. Earlier digits weigh more, so a big digit near the front costs the most. Keep the digits in a stack that only rises. When a smaller digit arrives and removals remain, pop the bigger top. It's the monotonic stack, used greedily.

For each digit, while k is left and the top is bigger, pop it and spend one. Then push the digit. Leftover removals come off the end. Strip leading zeros, and return zero if empty.

Now one, four, three, two, two, one, nine, with three removals. One and four go on. Three pops the four. Two pops the three. The next two is equal, so it stays. One pops a two: that's the last removal. One and nine go on. Answer: one, two, one, nine.

Each digit is pushed once and popped at most once: linear time. The stack can hold all n digits: linear space.

Scan, pop the bigger tops, strip the zeros. That's Remove K Digits.