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
ndigits.
- In the worst case, the stack may store up to