Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.


Note:

The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.




Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.



Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.



Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Difficulty: interview

Starter code:

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        

Solutions:
class Solution:
     def removeKdigits(self, num, k):
         """
         :type num: str
         :type k: int
         :rtype: str
         """
         out=[]
         for digit in num:
             while k and out and out[-1] > digit:
                 out.pop()
                 k-=1
             out.append(digit)
         return ''.join(out[:-k or None]).lstrip('0') or "0"

class Solution:
     def removeKdigits(self, num, k):
         """
         :type num: str
         :type k: int
         :rtype: str
         """
         if(num == ""): return ""
         arr = [i for i in list(num)]
         stack = [arr[0]]
         out = 0
         for i in range(1, len(arr)):
             while(out < k and len(stack)>0 and arr[i] < stack[-1]):
                 stack.pop()
                 out += 1
             stack.append(arr[i])
         diff = k - out
         for i in range(diff): stack.pop()
         res = "".join(stack).lstrip("0")
         if(res == ""): return "0"
         return res


class Solution(object):
     def removeKdigits(self, num, k):
         """
         :type num: str
         :type k: int
         :rtype: str
         """
         if k == len(num):
             return "0"
         stack = []
         cnt = 0
         for i, ch in enumerate(num):
             if cnt == k:
                 for j in range(i, len(num)):
                     stack.append(num[j])
                 break
             if not stack or ch >= stack[-1]:
                 stack.append(ch)
             else:
                 while stack and ch < stack[-1] and cnt < k:
                     stack.pop()
                     cnt += 1
                 stack.append(ch)
         while cnt < k:
             stack.pop()
             cnt += 1
         i = 0
         while i < len(stack) and stack[i] == '0':
             i += 1
         if i == len(stack):
             return "0"
         return ''.join(stack[i:])

class Solution:
     def removeKdigits(self, num, k):
         """
         :type num: str
         :type k: int
         :rtype: str
         """
         while True:
             if k == 0:
                 return num if num != "" else "0"
             if num == "":
                 return "0"
             index = 0
             num_len = len(num)
             while True:
                 if index == num_len - 1:
                     num = num[:-1]
                     k -= 1
                     break
                 if num[index] > num[index + 1]:
                     new_num = num[:index] + num[index+1:]
                     num = new_num.lstrip("0")
                     k -= 1
                     break
                 index += 1

class Solution:
     def removeKdigits(self, num, k):
         """
         :type num: str
         :type k: int
         :rtype: str
         """
         stack = []
         i = 0
         num += '0'
         while i < len(num):
             while stack and stack[-1] > num[i] and k > 0:
                 stack.pop()
                 k -= 1
             if (stack or num[i] != '0') and i < len(num)-1:     
                 stack.append(num[i]) 
             i += 1
         res = ''.join(stack)
         return res if res else '0'