Remove K digits

"""
Key intuition:
If a larger digit appears before a smaller digit (e.g., ... 4 3 ...),
keeping the larger digit will always lead to a bigger number.
Therefore, whenever we encounter such a pattern and still have removals
available, it is always optimal to remove the larger digit on the left.

Approach:
We use a monotonic increasing stack to build the smallest possible number.
The stack maintains digits in increasing order from left to right, ensuring
that higher place-value positions are as small as possible.

Algorithm:
- Iterate through each digit in the number.
- While the stack is not empty, removals (k) are still available, and the
  top of the stack is greater than the current digit, pop the stack
  (this removes a larger digit that would worsen the final number).
- Push the current digit onto the stack.
- After processing all digits, if removals remain, remove digits from the
  end of the stack (least significant digits).
- Finally, strip leading zeros. If the result is empty, return "0".

Invariant:
At every step, the stack represents the smallest possible prefix that can
be formed using the digits processed so far with the remaining removals.
"""

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        st = []

        for i in num:
            while st and k > 0 and st[-1] > i:
                st.pop()
                k -= 1
            st.append(i)

        # If removals remain, remove from end
        while k > 0:
            st.pop()
            k -= 1

        # Build result and remove leading zeros
        result = "".join(st).lstrip('0')

        return result if result else "0"