Problem statement

https://leetcode.com/problems/remove-k-digits/

Solution

The idea is to build the biggest number using stack and greedy algorithm. Traverse all digits from num and for each of them check if it is worth to remove first some last digits from our stack: if we removed digit, decrease attempt (equal to k at the beginning) by 1. In the end we possibly need to remove some last symbols, so overall we have k removed symbols and also remove all leading zeroes.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def removeKdigits(self, num, k):
        attempts, stack = k, []
        
        for digit in num:
            while stack and digit < stack[-1] and attempts > 0:
                stack.pop()
                attempts -= 1
            stack.append(digit)
        
        out = "".join(stack[0:len(num)-k]).lstrip("0")
        return "0" if out == "" else out