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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def removeKdigits(self, num, k):
		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):
		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):
		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):
		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):
		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'