Remove K Digits - Solution
Solutions and explanations

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []  # Monotonic Increasing Stack
        deleted_cnt = 0
        for digit in num:
            while stack and stack[-1] > digit and deleted_cnt < k:
                stack.pop()
                deleted_cnt += 1
            stack.append(digit)
        
        while stack and deleted_cnt < k:
            stack.pop()
            deleted_cnt += 1
        
        res = "".join(stack)
        return res.lstrip("0") or "0" # Remove leading zeros

Complexity Analysis

Here, n is the length of the input string.

  • Time Complexity: O(n)
    • Each digit is pushed onto the stack at most once and popped at most once, with constant work per operation, resulting in overall linear time..
  • Space Complexity: O(n)
    • In the worst case, the stack may store up to n digits.