Remove K Digits (hard)

Problem Statement

Given a non-negative integer represented as a string num and an integer k, delete k digits from num to obtain the smallest possible integer. Return this minimum possible integer as a string.

Examples

- Input: num = "1432219", k = 3
- Output: "1219"
- Explanation: The digits removed are 4, 3, and 2 forming the new number 1219 which is the smallest.
- Input: num = "10200", k = 1
- Output: "200"
- Explanation: Removing the leading 1 forms the smallest number 200.
- Input: num = "1901042", k = 4

.....

Like the course? Get enrolled and start learning!

Mohammed Dh Abbas

· 2 years ago

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

        for d in num:
            # while the number is smaller that the top of stack keep popping
            while count < k and len(stack) > 0 and int(d) < int(stack[-1]):
                stack.pop()
                count += 1

            # don't insert 0 if the stack is empty otherwise insert 
            if len(stack) == 0:
                if int(d) > 0:
                    stack.append(d)
            else:
                stack.append(d)

        # remaining number that needs to be popped out to meet k 
        while len(stack) > 0 and count < k:
            count += 1
            stack.pop()

        result = "".join(stack) 

        # empty string mean