Given a non-negative integer S represented as a string, remove K digits from the number so that the new number is the smallest possible.
Note : The given num does not contain any leading zero.
Example 1:
Input:
S = "149811", K = 3
Output: 111
Explanation: Remove the three digits 
4, 9, and 8 to form the new number 111
which is smallest.
Example 2:
Input:
S = "1002991", K = 3
Output: 21
Explanation: Remove the three digits 1(leading
one), 9, and 9 to form the new number 21(Note
that the output must not contain leading
zeroes) which is the smallest.
Your Task:
You don't need to read input or print anything. Your task is to complete the function removeKdigits() which takes the string S and an integer K as input and returns the new number which is the smallest possible.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1<=|S|<=10002
1<=K<=|S|

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:

    def removeKdigits(self, S, K):
        # code here

Solutions:
class Solution:

	def removeKdigits(self, S, K):
		stack = [S[0]]
		for i in S[1:]:
			while K > 0 and stack and (i < stack[-1]):
				stack.pop()
				K -= 1
			stack.append(i)
		stack = stack[:len(stack) - K]
		ans = ''.join(stack)
		return str(int(ans))


class Solution:

	def removeKdigits(self, S, K):
		ans = []
		for c in S:
			while len(ans) and ans[-1] > c and (K > 0):
				ans.pop()
				K -= 1
			if len(ans) > 0 or c != '0':
				ans.append(c)
		while len(ans) and K > 0:
			K -= 1
			ans.pop()
		if len(ans) == 0:
			return '0'
		S2 = ''
		for c in ans:
			S2 += c
		return S2


class Solution:

	def removeKdigits(self, arr, k):
		stack = [arr[0]]
		for i in arr[1:]:
			while len(stack) > 0 and k > 0 and (stack[-1] > i):
				stack.pop()
				k -= 1
			stack.append(i)
		stack = stack[:len(stack) - k]
		ans = ''.join(stack)
		return str(int(ans))


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		for n in S:
			while stack and K > 0 and (stack[-1] > n):
				stack.pop()
				K -= 1
			if stack or n is not '0':
				stack.append(n)
		if K:
			stack = stack[0:-K]
		return ''.join(stack) or '0'


class Solution:

	def removeKdigits(self, S, K):
		answer = ''
		for ch in S:
			while answer and answer[-1] > ch and (K > 0):
				answer = answer[:-1]
				K -= 1
			if answer or ch != '0':
				answer += ch
		while answer and K > 0:
			answer = answer[:-1]
			K -= 1
		if not answer:
			return '0'
		return answer


class Solution:

	def removeKdigits(self, S, k):
		n = len(S)
		st = []
		for i in range(n):
			while len(st) != 0 and S[i] < st[-1] and (k > 0):
				st.pop()
				k -= 1
			if len(st) != 0 or S[i] != 0:
				st.append(S[i])
			if len(st) == 1 and st[-1] == '0':
				st.pop()
		while len(st) != 0 and k > 0:
			k -= 1
			st.pop()
		if len(st) == 0:
			return '0'
		res = ''
		while len(st) != 0:
			z = st[-1]
			st.pop()
			res = z + res
		return res


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		for c in S:
			while K > 0 and stack and (stack[-1] > c):
				K -= 1
				stack.pop()
			stack.append(c)
		stack = stack[:len(stack) - K]
		res = ''.join(stack)
		return str(int(res))


class Solution:

	def removeKdigits(self, s, k):
		st = []
		for el in s:
			if not st and el == '0':
				continue
			elif not st:
				st.append(el)
			elif st[-1] <= el:
				st.append(el)
			else:
				while st and st[-1] > el and (k > 0):
					st.pop()
					k -= 1
				if not st and el == '0':
					continue
				st.append(el)
		if k > len(st):
			return 0
		if k > 0 and st:
			st = st[:len(st) - k]
		if not st:
			return 0
		return ''.join(st)


788
7
78
788

class Solution:

	def removeKdigits(self, S, K):
		stack = []
		for el in S:
			while stack and K and (stack[-1] > el):
				stack.pop()
				K -= 1
			stack.append(el)
		for i in range(K):
			stack.pop()
		return int(''.join(stack))


class Solution:

	def removeKdigits(self, S, k):
		l = len(S)
		ans = ''
		st = []
		for i in range(l):
			while st and k > 0 and (st[-1] > S[i]):
				st.pop()
				k -= 1
			st.append(S[i])
		if k > 0:
			while k > 0:
				st.pop()
				k -= 1
		while st:
			ans = st[-1] + ans
			st.pop()
		i = 0
		while i < len(ans) and ans[i] == '0':
			i += 1
		ans = ans[i:]
		if not ans:
			return '0'
		return ans


class Solution:

	def removeKdigits(self, S, K):
		s = []
		for c in S:
			while len(s) > 0 and s[-1] > c and (K > 0):
				s.pop()
				K -= 1
			s.append(c)
		while K > 0:
			s.pop()
			K -= 1
		start = len(s)
		for i in range(len(s)):
			if s[i] != '0':
				start = i
				break
		if start == len(s):
			return '0'
		return ''.join(s[start:])


class Solution:

	def removeKdigits(self, S, K):
		stack = list()
		for i in range(len(S)):
			if K == 0:
				stack.append(S[i])
				continue
			if i == 0:
				if S[i] == 0:
					continue
				else:
					stack.append(S[i])
			else:
				current = S[i]
				while K > 0 and stack and (current < stack[-1]):
					stack.pop()
					K -= 1
				if current != 0:
					stack.append(current)
		while K > 0 and stack:
			stack.pop()
			K -= 1
		number = ''
		for i in range(len(stack)):
			number += stack[i]
		if number:
			return int(number)
		return 0


class Solution:

	def removeKdigits(self, S, K):
		s = []
		for i in S:
			while K > 0 and s and (s[-1] > i):
				K -= 1
				s.pop()
			s.append(i)
		s = s[:len(s) - K]
		res = ''.join(s)
		return str(int(res)) if res else '0'


class Solution:

	def removeKdigits(self, S, K):
		s = []
		ans = ''
		n = len(S)
		for i in range(n):
			while s and s[-1] > S[i] and (K > 0):
				s.pop()
				K = K - 1
			s.append(S[i])
		while K > 0 and s:
			s.pop()
			K = K - 1
		while s:
			ans = s.pop() + ans
		index = 0
		while index < len(ans) and ans[index] == '0':
			index = index + 1
		if index < len(ans):
			return ans[index:]
		return '0'


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		i = 0
		while K > 0 and i < len(S):
			if stack == []:
				stack.append(S[i])
				i += 1
			elif stack[-1] > S[i]:
				stack.pop()
				K -= 1
			elif stack[-1] <= S[i]:
				stack.append(S[i])
				i += 1
		while i < len(S):
			stack.append(S[i])
			i += 1
		str = ''
		for i in stack:
			str += i
		if K > 0:
			str = str[:-K]
		return int(str)


class Solution:

	def removeKdigits(self, num, k):
		st = []
		if len(num) <= k:
			return '0'
		for i in range(len(num)):
			if len(st) == 0:
				st.append(num[i])
			else:
				while len(st) and st[-1] > num[i] and (k > 0):
					st.pop()
					k -= 1
				st.append(num[i])
		while k > 0:
			st.pop()
			k -= 1
		res = ''
		if len(st) == 0:
			return '0'
		for i in range(len(st)):
			res += st[i]
		res = int(res)
		return str(res)


class Solution:

	def removeKdigits(self, s, k):
		stk = []
		res = []
		ans = ''
		n = len(s)
		for i in range(n - 1, -1, -1):
			while len(stk) > 0 and s[i] <= s[stk[-1]]:
				stk.pop()
			if len(stk) == 0:
				res.append(n)
			else:
				res.append(stk[-1])
			stk.append(i)
		res = res[::-1]
		for i in range(n):
			res[i] = res[i] - i
		i = 0
		while i < n:
			if s[i] == '0':
				ans += '0'
				i += 1
			elif res[i] <= k:
				k -= res[i]
				i += res[i]
			else:
				ans += s[i]
				i += 1
		cnt0 = 0
		i = 0
		f = 0
		while i < len(ans) and ans[i] == '0':
			if ans[i] == '0':
				cnt0 += 1
				i += 1
			else:
				f = 1
				break
		if i == len(ans) or len(ans) == 0:
			return '0'
		return ans[i:]


class Solution:

	def removeKdigits(self, s, k):
		if k >= len(s):
			return 0
		if k == 0:
			return s
		st = [s[0]]
		for i in s[1:]:
			while k > 0 and st and (i < st[-1]):
				st.pop()
				k -= 1
			st.append(i)
		st = st[:len(st) - k]
		return int(''.join(st))


class Solution:

	def removeKdigits(self, a, k):
		st = []
		ans = ''
		n = len(a)
		for c in a:
			while st and k > 0 and (int(c) < int(st[-1])):
				st.pop()
				k -= 1
			if st or c != '0':
				st.append(c)
		while st and k:
			st.pop()
			k -= 1
		if not st:
			return '0'
		for i in range(len(st)):
			ans += st[i]
		return ans


class Solution:

	def removeKdigits(self, s, k):
		n = len(s)
		if n == k:
			return 0
		stack = []
		stack.append(s[0])
		for i in range(1, n):
			while stack and s[i] < stack[-1] and (k > 0):
				stack.pop()
				k -= 1
			stack.append(s[i])
		while stack and k > 0:
			stack.pop()
			k -= 1
		ans = ''.join(stack)
		return int(ans)


class Solution:

	def removeKdigits(self, num, n):
		stack = []
		for i in range(len(num)):
			while stack and n > 0 and (stack[-1] > num[i]):
				stack.pop()
				n -= 1
			if n <= 0:
				break
			stack.append(num[i])
		if n <= 0:
			for k in range(i, len(num)):
				stack.append(num[k])
		else:
			while n > 0:
				stack.pop()
				n -= 1
		res = ''
		for i in stack:
			res += i
		return int(res)


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		if K > len(S):
			return '0'
		n = len(S)
		for i in range(n):
			while stack and int(stack[-1]) > int(S[i]) and (K > 0):
				stack.pop()
				K -= 1
			stack.append(S[i])
		while stack and K > 0:
			stack.pop()
			K -= 1
		ans = ''.join(stack).lstrip('0')
		if ans == '' or ans == '0' or K > 0 or (len(ans) < 1):
			return '0'
		else:
			return ans


class Solution:

	def removeKdigits(self, S, K):
		if len(S) == K:
			return '0'
		stack = []
		for n in S:
			while stack and K and (int(stack[-1]) > int(n)):
				stack.pop()
				K -= 1
			stack.append(n)
		while K:
			stack.pop()
			K -= 1
		if not stack:
			return '0'
		return str(int(''.join(stack)))


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		for x in S:
			while stack and int(stack[-1]) > int(x) and (K != 0):
				stack.pop()
				K -= 1
			stack.append(x)
		while K != 0:
			stack.pop()
			K -= 1
		return ''.join(stack).lstrip('0') or 0


class Solution:

	def removeKdigits(self, s, k):
		st = []
		for i in s:
			while st and k > 0 and (st[-1] > i):
				st.pop()
				k -= 1
			st.append(i)
		if k:
			st = st[0:-k]
		res = ''.join(st)
		return str(int(res)) if res else '0'


class Solution:

	def removeKdigits(self, S, K):
		st = []
		for i in S:
			while st and K and (st[-1] > i):
				st.pop()
				K -= 1
			if st or i is not '0':
				st.append(i)
		if K:
			st = st[:-K]
		res = ''
		for ele in st:
			res += ele
		if res == '':
			return 0
		return res


class Solution:

	def removeKdigits(self, S, K):
		l = len(S)
		stack = []
		for i in S:
			while len(stack) > 0 and K > 0 and (stack[-1] > i):
				stack.pop()
				K -= 1
			if len(stack) > 0 or i != '0':
				stack.append(i)
		while len(stack) > 0 and K:
			K -= 1
			stack.pop()
		if len(stack) == 0 or len(stack) == K:
			return '0'
		s = ''
		for i in stack:
			s += i
		return s


class Solution:

	def removeKdigits(self, S, K):
		s = []
		n = len(S)
		for i in S:
			while s and K > 0 and (s[-1] > i):
				s.pop()
				K -= 1
			if s or i != '0':
				s.append(i)
		while s and K:
			s.pop()
			K -= 1
		if len(s) == 0:
			return '0'
		S = list(S)
		while s:
			S[n - 1] = s[-1]
			s.pop()
			n -= 1
		return ''.join(S[n:])


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		stack.append(S[0])
		for i in range(1, len(S)):
			while (K > 0 and len(stack) > 0) and S[i] < stack[-1]:
				stack.pop()
				K -= 1
			stack.append(S[i])
		while K != 0:
			stack.pop()
			K -= 1
		res = ''
		i = 0
		while i < len(stack):
			if stack[0] == '0':
				stack.pop(0)
				i -= 1
			else:
				res += stack[i]
			i += 1
		if res == '':
			return 0
		return res


class Solution:

	def removeKdigits(self, S, K):
		st = []
		for n in S:
			while K > 0 and len(st) > 0 and (st[-1] > n):
				K -= 1
				st.pop()
			st.append(n)
		st = st[:len(st) - K]
		ans = ''.join(st)
		return str(int(ans)) if ans else '0'


class Solution:

	def removeKdigits(self, S, k):
		stack = []
		for i in S:
			while stack and stack[-1] > i and (k > 0):
				stack.pop()
				k = k - 1
			if len(stack) != 0 or i != '0':
				stack.append(i)
		while len(stack) != 0 and k > 0:
			stack.pop()
			k = k - 1
		if len(stack) == 0:
			return '0'
		S = ''
		for i in stack:
			S = S + i
		return S


class Solution:

	def removeKdigits(self, S, K):
		stack = ['0']
		for item in S:
			while K and stack[-1] > item:
				stack.pop()
				K -= 1
			stack.append(item)
		return int(''.join(stack[:-K])) if K else int(''.join(stack))


class Solution:

	def removeKdigits(self, S, k):
		stack = []
		for i in range(len(S)):
			while k > 0 and stack and (stack[-1] > S[i]):
				k -= 1
				stack.pop()
			stack.append(S[i])
		stack = stack[:len(stack) - k]
		res = ''.join(stack)
		return str(int(res)) if res else '0'


class Solution:

	def removeKdigits(self, num, k):
		s = []
		for i in num:
			while s and int(i) < s[-1] and (k != 0):
				s.pop()
				k -= 1
			s.append(int(i))
		while k:
			s.pop()
			k -= 1
		ans = ''
		for j in s:
			ans += str(j)
		return ans.lstrip('0') or '0'


class Solution:

	def removeKdigits(self, S, K):
		stack = '0'
		while K:
			if not S:
				return int(stack[:-K])
			elif stack[-1] > S[0]:
				stack = stack[:-1]
				K -= 1
			else:
				stack += S[0]
				S = S[1:]
		return int(stack + S)


class Solution:

	def removeKdigits(self, s, k):
		num = ''
		num = s
		st = list()
		for n in num:
			while st and k and (st[-1] > n):
				st.pop()
				k -= 1
			if st or n is not '0':
				st.append(n)
		if k:
			st = st[0:-k]
		return ''.join(st) or '0'


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		for i in S:
			while K > 0 and len(stack) > 0 and (stack[-1] > i):
				stack.pop()
				K -= 1
			if len(stack) > 0 or i != '0':
				stack.append(i)
		while len(stack) > 0 and K > 0:
			stack.pop()
			K -= 1
		if len(stack) == 0:
			return '0'
		else:
			return ''.join(stack)


class Solution:

	def removeKdigits(self, arr, k):
		n = len(arr)
		stk = []
		for i in arr:
			while stk and k > 0 and (int(stk[-1]) > int(i)):
				stk.pop()
				k -= 1
			if stk or int(i) > 0:
				stk.append(i)
		while stk and k > 0:
			k -= 1
			stk.pop()
		if len(stk) == 0:
			return 0
		word = ''
		for i in stk:
			word += i
		return word


class Solution:

	def removeKdigits(self, num, k):
		if k == len(num):
			return '0'
		stack = []
		for i in range(len(num)):
			while stack and k > 0 and (num[stack[-1]] > num[i]):
				stack.pop()
				k -= 1
			stack.append(i)
		while k > 0 and stack:
			stack.pop()
			k -= 1
		answer = ''
		for i in range(len(stack)):
			if num[stack[i]] != '0' or answer != '':
				answer += num[stack[i]]
		return '0' if answer == '' else answer


class Solution:

	def removeKdigits(self, S, N):
		s = []
		for i in S:
			while s and s[-1] > i and (N > 0):
				s.pop()
				N -= 1
			s.append(i)
		t = ''.join(s)
		t = t.lstrip('0')
		if len(t) == 0:
			return '0'
		if N > 0:
			if len(t) <= N:
				return '0'
			return t[:-N]
		return t


class Solution:

	def removeKdigits(self, S, K):
		st = []
		for i in S:
			ele = int(i)
			while len(st) and K > 0 and (ele < st[-1]):
				st.pop()
				K = K - 1
			if ele != 0 or len(st) != 0:
				st.append(ele)
		while len(st) and K > 0:
			st.pop()
			K = K - 1
		if len(st) == 0:
			return '0'
		return ''.join([str(item) for item in st])


class Solution:

	def removeKdigits(self, s, k):
		s = list(s)
		stack = [s[0]]
		n = len(s)
		index = n
		for i in range(1, n):
			if k == 0:
				index = i
				break
			if len(stack) == 0 or stack[-1] < s[i]:
				stack.append(s[i])
			else:
				while k > 0 and stack and (stack[-1] > s[i]):
					stack.pop()
					k -= 1
				stack.append(s[i])
		if index < n:
			return int(''.join(stack + s[index:]))
		if k > 0:
			return int(''.join(stack[:len(stack) - k]))
		return int(''.join(stack))


class Solution:

	def removeKdigits(self, num, k):
		stack = []
		l = list(num)
		if k == len(l):
			return '0'
		for i in l:
			if k == 0:
				stack.append(i)
			elif stack == []:
				stack.append(i)
			elif stack[-1] <= i:
				stack.append(i)
			elif stack[-1] > i:
				while stack != [] and stack[-1] > i and (k > 0):
					stack.pop()
					k -= 1
				stack.append(i)
		if k != 0:
			for i in range(k):
				stack.pop()
		if stack == []:
			return '0'
		else:
			res = ''
			for i in stack:
				res += i
			i = int(res)
			s = str(i)
			return s


class Solution:

	def removeKdigits(self, S, K):
		numStack = []
		for num in S:
			while K > 0 and len(numStack) > 0 and (num < numStack[-1]):
				numStack.pop()
				K -= 1
			else:
				numStack.append(num)
		if K > 0:
			for _ in range(K):
				numStack.pop()
		return int(''.join(numStack))


class Solution:

	def removeKdigits(self, S, K):
		res = []
		counter = 0
		n = len(S)
		if n == K:
			return '0'
		for i in range(n):
			while K and res and (res[-1] > S[i]):
				res.pop()
				K -= 1
			res.append(S[i])
		while K:
			res.pop()
			K -= 1
		return ''.join(res).lstrip('0') or '0'


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		S = int(S)
		S = str(S)
		for i in S:
			if len(stack) == 0:
				stack.append(i)
			else:
				num = stack[-1]
				while num > i and K > 0:
					x = stack.pop()
					K -= 1
					if len(stack) > 0:
						num = stack[-1]
					else:
						break
				stack.append(i)
		while K > 0:
			stack.pop()
			K = K - 1
		if len(stack) == 0:
			stack = [0]
			return '0'
		result = ''.join(stack)
		result = int(result)
		result = str(result)
		return result


class Solution:

	def removeKdigits(self, s, k):
		if k == len(s):
			return '0'
		stack = []
		for dig in s:
			while len(stack) > 0 and dig < stack[-1] and (k > 0):
				stack.pop()
				k -= 1
			stack.append(dig)
		while k > 0:
			stack.pop()
			k -= 1
		stack = stack[::-1]
		while len(stack) > 0 and stack[-1] == '0':
			stack.pop()
		stack = stack[::-1]
		return ''.join(stack) if len(stack) > 0 else '0'


class Solution:

	def removeKdigits(self, s, k):
		stk = []
		for c in s:
			while k > 0 and stk and (stk[-1] > c):
				r = stk.pop()
				if c == 0 and r == 0:
					continue
				k -= 1
			stk.append(c)
		stk = stk[:len(stk) - k]
		res = ''.join(stk)
		return str(int(res)) if res else '0'


class Solution:

	def removeKdigits(self, S, K):
		stk = []
		for i in range(len(S)):
			while K > 0 and stk and (stk[-1] > S[i]):
				stk.pop()
				K -= 1
			stk.append(S[i])
		stk = stk[:len(stk) - K]
		ans = ''.join(stk).lstrip('0')
		if ans == '':
			return '0'
		return ans


class Solution:

	def removeKdigits(self, s, k):
		stack = []
		for i in s:
			while stack and stack[-1] > i and (k > 0):
				stack.pop()
				k -= 1
			stack.append(i)
		stack = stack[:len(stack) - k]
		r = ''.join(stack)
		return str(int(r))


class Solution:

	def removeKdigits(self, S, k):
		arr = []
		for r in S:
			arr.append(r)
		ans = ''
		stck = []
		lis = []
		i = 0
		while i < len(arr):
			if k > 0:
				if arr[i] == 0:
					i += 1
					pass
				if len(stck) == 0:
					stck.append(arr[i])
					i += 1
				elif stck[-1] > arr[i]:
					lis.append(stck.pop())
					k -= 1
				else:
					stck.append(arr[i])
					i += 1
			else:
				break
		while k > 0:
			lis.append(stck.pop())
			k -= 1
		for q in lis:
			arr.remove(q)
		while 0 in arr:
			arr.remove(0)
		for w in arr:
			ans += str(w)
		return int(ans)


class Solution:

	def removeKdigits(self, s, k):
		st = []
		for x in s:
			while st and k and (st[-1] > x):
				st.pop()
				k -= 1
			if x != '0' or st:
				st.append(x)
		while st and k:
			st.pop()
			k -= 1
		if not st:
			return 0
		return ''.join(st)


class Solution:

	def removeKdigits(self, num, k):
		numStack = []
		for digit in num:
			while k and numStack and (numStack[-1] > digit):
				numStack.pop()
				k -= 1
			numStack.append(digit)
		finalStack = numStack[:-k] if k else numStack
		return ''.join(finalStack).lstrip('0') or '0'


class Solution:

	def removeKdigits(self, S, K):
		stack = [S[0]]
		for i in S[1:]:
			while stack and K and (i < stack[-1]):
				K -= 1
				stack.pop()
			stack.append(i)
		if K:
			for i in range(K):
				stack.pop()
		return int(''.join(stack))


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		for elem in S:
			while K > 0 and len(stack) > 0 and (stack[-1] > elem):
				stack.pop()
				K -= 1
			stack.append(elem)
		while K > 0:
			stack.pop()
			K -= 1
		ans = ''
		while stack:
			x = stack.pop(0)
			ans += x
		newans = int(ans)
		return str(newans)


class Solution:

	def removeKdigits(self, S, k):
		stack = []
		for digit in S:
			while k > 0 and stack and (stack[-1] > digit):
				stack.pop()
				k -= 1
			stack.append(digit)
		stack = stack[:len(stack) - k]
		string = ''.join(stack)
		return int(string) if string else ''


class Solution:

	def removeKdigits(self, S, K):
		stack = []
		ans = ''
		for i in range(len(S)):
			while len(stack) != 0 and K != 0 and (stack[-1] > int(S[i])):
				stack.pop()
				K -= 1
			if len(stack) == 0 and int(S[i]) == 0:
				continue
			else:
				stack.append(int(S[i]))
		while len(stack) != 0 and K != 0:
			stack.pop()
			K -= 1
		if len(stack) == 0:
			return '0'
		for i in range(len(stack) - 1, -1, -1):
			ans = str(stack[i]) + ans
		i = 0
		while ans[i] == '0':
			i += 1
		return ans[i:]


class Node:

	def __init__(self, v):
		self.v = v
		self.prev = self.next = None

class Solution:

	def removeKdigits(self, S, K):
		guard = Node(-1)
		p = guard
		for c in S:
			nd = Node(int(c))
			p.next = nd
			nd.prev = p
			p = nd
		nd = guard.next
		while nd and nd.next and (K > 0):
			if nd.v > nd.next.v:
				(nex, npr) = (nd.next, nd.prev)
				npr.next = nex
				nex.prev = npr
				nd.next = nd.prev = None
				nd = npr
				K -= 1
			else:
				nd = nd.next
		nd = guard.next
		while nd and nd.v == 0:
			nd = nd.next
		out = []
		while nd:
			out.append(str(nd.v))
			nd = nd.next
		ans = ''.join(out)
		if len(ans) <= K:
			return '0'
		else:
			return ans[:len(ans) - K]