402 Remove K Digits

Code:

Python3

class Solution:
    def removeKdigits(self,num, k):
        stack = []
        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
 
        # If k is still greater than 0, remove remaining digits from the end
        stack = stack[:-k] if k else stack
 
        # Remove leading zeros
        return ''.join(stack).lstrip('0') or '0'

Big O Analysis

• Runtime The runtime complexity here is $O(n)wheren=s.length$.
• Memory The memory usage is $O(1)$. Although we are using an array count, its always going to be of length 26, constant space!.

— A

GitHub | Twitter