Given a number k and string num of digits (0 to 9) denoting a positive integer. Find a string denoting the lowest integer number possible by removing k digits from num, without changing their order.
Note: num will not contain any leading zero.
 
Example 1:
Input:
k = 2
num = "143729"
Output: "1329"
Explanation: 1329 is the minimum number
possible after removing '4' and '7'.
 
Example 2:
Input:
k = 3
num = "10056"
Output: "0"
Explanation: 0 is the minimum number
possible after removing '1' , '5' and '6'.
 
Your Task:  
You dont need to read input or print anything. Complete the function buildLowestNumber() which accepts string num and integer k as input parameters and returns a string denoting the smallest integer possible after removing k digits from num without changing the order.
Expected Time Complexity: O(Length of num) 
Expected Auxiliary Space: O(Length of num) 
Constraints:
1 <= Length of num <= 10^{5}
0 <= k < Length of num

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:



    def buildLowestNumber(self, S,N):

        # code here

Solutions:
class Solution:

	def buildLowestNumber(self, S, k):
		st = []
		st.append(int(S[0]))
		length = len(S)
		for i in range(1, length):
			num = int(S[i])
			while len(st) != 0 and k > 0 and (num < st[-1]):
				st.pop()
				k = k - 1
			st.append(num)
		while len(st) != 0 and k > 0:
			st.pop()
			k = k - 1
		ans = ''
		li = list(map(str, st))
		while li and li[0] == '0':
			li.pop(0)
		if li:
			ans = ''.join(li)
			return ans
		return '0'


class Solution:

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


class Solution:

	def buildLowestNumber(self, S, N):
		n = len(S)
		stack = [int(S[0])]
		for i in range(1, n):
			curr_num = int(S[i])
			while stack and N > 0 and (curr_num < stack[-1]):
				N -= 1
				stack.pop()
			stack.append(curr_num)
		while N > 0 and stack:
			stack.pop()
			N -= 1
		ans = ''
		while len(stack) > 0:
			ans += str(stack.pop())
		return int(ans[::-1])


class Solution:

	def buildLowestNumber(self, S, N):
		s = []
		for i in S:
			if s == []:
				s.append(int(i))
			else:
				while N > 0 and s and (int(i) < s[-1]):
					s.pop()
					N -= 1
				s.append(int(i))
		while N > 0:
			s.pop()
			N -= 1
		res = ''
		for i in s:
			res += str(i)
		return int(res)


class Solution:

	def buildLowestNumber(self, S, N):
		count = 0
		stack = [S[0]]
		length = len(S)
		for i in range(1, length):
			if count == N:
				break
			if S[i] < stack[-1]:
				while stack != [] and count < N:
					if stack[-1] > S[i]:
						stack.pop()
						count += 1
					else:
						break
				stack.append(S[i])
				if count == N:
					break
			else:
				stack.append(S[i])
		if count == N:
			for j in range(i + 1, length):
				stack.append(S[j])
		else:
			while count < N and stack != []:
				stack.pop()
				count += 1
		return str(int(''.join(stack)))


class Solution:

	def buildLowestNumber(self, S, N):
		stack = []
		i = 0
		while N and i < len(S):
			if stack and stack[-1] > S[i]:
				stack.pop()
				N -= 1
			else:
				stack.append(S[i])
				i += 1
		while N:
			stack.pop()
			N -= 1
		return str(int(''.join(stack) + S[i:]))


class Solution:

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


class Solution:

	def buildLowestNumber(self, S, K):
		n = len(S)
		stack = []
		for i in range(n):
			while stack and K and (stack[-1] > S[i]):
				stack.pop()
				K -= 1
			if not stack and S[i] == '0':
				continue
			stack.append(S[i])
		while stack and K:
			K -= 1
			stack.pop()
		return ''.join(stack) if stack else '0'


class Solution:

	def buildLowestNumber(self, S, N):
		stack = list()
		for num in S:
			while stack and N and (int(stack[-1]) > int(num)):
				stack.pop()
				N -= 1
			stack.append(num)
		while N:
			stack.pop()
			N -= 1
		res = ''.join(stack)
		res = res.lstrip('0')
		return res if res else '0'


class Solution:

	def buildLowestNumber(self, num, k):
		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 buildLowestNumber(self, str, k):
		x = []
		for i in str:
			while x and int(x[-1]) > int(i) and (k != 0):
				x.pop()
				k = k - 1
			x.append(i)
		while x and k != 0:
			x.pop()
			k = k - 1
		while x and x[0] == '0':
			x.remove('0')
		ans = ''
		for i in x:
			ans = ans + i
		if ans == '':
			return '0'
		return ans


class Solution:

	def buildLowestNumber(self, S, N):
		stack = []
		for num in S:
			st_len = len(stack)
			while N > 0 and stack and (stack[-1] > num):
				stack.pop()
				N -= 1
			stack.append(num)
		while N > 0 and stack and (stack[-1] > '0'):
			stack.pop()
			N -= 1
		while len(stack) != 0 and stack[0] == '0':
			del stack[0]
		ans = ''.join(stack)
		return '0' if not ans else ans


class Solution:

	def buildLowestNumber(self, num, k):
		n = len(num)
		mystack = []
		for c in num:
			while len(mystack) > 0 and k > 0 and (ord(mystack[len(mystack) - 1]) > ord(c)):
				mystack.pop()
				k -= 1
			if len(mystack) > 0 or c != '0':
				mystack.append(c)
		while len(mystack) > 0 and k:
			mystack.pop()
			k -= 1
		if len(mystack) == 0:
			return '0'
		num = list(num)
		while len(mystack) > 0:
			num[n - 1] = mystack[len(mystack) - 1]
			mystack.pop()
			n -= 1
		return ''.join(num[n:])


class Solution:

	def buildLowestNumber(self, S, N):
		stack = []
		for i in range(len(S)):
			num = int(S[i])
			while stack and N > 0 and (num < stack[-1]):
				stack.pop()
				N -= 1
			stack.append(num)
		while stack and N > 0:
			stack.pop()
			N -= 1
		res = ''.join([str(i) for i in stack])
		return str(int(res))


class Solution:

	def buildLowestNumber(self, S, N):
		stack = []
		for i in S:
			if len(stack) and stack[-1] > i:
				while N > 0 and len(stack) and (stack[-1] > i):
					stack.pop()
					N -= 1
				stack.append(i)
			else:
				stack.append(i)
		while N > 0:
			stack.pop()
			N -= 1
		ans = ''.join(stack)
		result = ans.lstrip('0')
		if len(result) == 0:
			return '0'
		return result


class Solution:

	def buildLowestNumber(self, S, k):
		Sl = list(S)
		n = len(Sl)
		st = []
		for i in S:
			while len(st) > 0 and st[-1] > i and (k > 0):
				st.pop()
				k -= 1
			st.append(i)
		while k > 0:
			st.pop()
			k -= 1
		ans = ''.join(st)
		return int(ans)


class Solution:

	def buildLowestNumber(self, S, N):
		num = []
		for i in S:
			num.append(int(i))
		req = len(num) - N
		num2 = []
		for i in range(len(num)):
			num2.append(num[i])
			while N != 0 and len(num2) > 1 and (num2[-2] > num2[-1]):
				num2.pop(-2)
				N = N - 1
		if len(num2) > req:
			for i in range(N):
				num2.pop()
		num = []
		for i in num2:
			num.append(str(i))
		st = ''.join(num)
		num = int(st)
		st = str(num)
		return st


class Solution:

	def buildLowestNumber(self, a, n):
		s = []
		if len(a) > 0:
			s.append(a[0])
		k = n
		i = 1
		while i < len(a):
			if k == 0:
				break
			while k > 0 and len(s) > 0 and (s[-1] > a[i]):
				s.pop()
				k -= 1
			if a[i] != 0:
				s.append(a[i])
			i += 1
		while i < len(a):
			s.append(a[i])
			i += 1
		if k > 0:
			s = s[:len(s) - k]
		while True:
			if len(s) > 0 and s[0] == '0':
				s.pop(0)
			else:
				break
		if len(s) == 0:
			return '0'
		ans = ''
		for y in s:
			ans += y
		return ans


class Solution:

	def buildLowestNumber(self, S, k):
		res = []
		for i in S:
			while len(res) > 0 and k > 0 and (res[len(res) - 1] > i):
				k -= 1
				res.pop()
			res += i
		while k > 0 and len(res) > 0:
			k -= 1
			res.pop()
		res = ''.join(res)
		for i in range(len(res)):
			if res[i] != '0':
				return res[i:]
		return '0'


class Solution:

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


class Solution:

	def buildLowestNumber(self, num: str, k: int) -> str:
		stack = []
		for i in range(len(num)):
			while stack and k > 0 and (stack[-1] > num[i]):
				stack.pop()
				k -= 1
			stack.append(num[i])
		while k > 0:
			stack.pop()
			k -= 1
		return ''.join(stack).lstrip('0') or '0'


class Solution:

	def buildLowestNumber(self, s, k):
		st = []
		(i, N) = (0, len(s))
		while i < N:
			while st and k and (st[-1] > s[i]):
				k -= 1
				st.pop()
			if st or s[i] != '0':
				st.append(s[i])
			i += 1
		while st and k:
			st.pop()
		if not st:
			return 0
		return ''.join(st)


class Solution:

	def buildLowestNumber(self, s, k):
		st = []
		n = 0
		(i, N) = (0, len(s))
		k = N - k
		while i < N:
			while st and n + N - i > k and (st[-1] > s[i]):
				st.pop()
				n -= 1
			st.append(s[i])
			n += 1
			i += 1
		while n > k:
			st.pop()
			n -= 1
		return int(''.join(st))


class Solution:

	def buildLowestNumber(self, S, N):

		def solve(S, N):
			stack = []
			for i in S:
				if not stack and i != '0':
					stack.append(i)
				elif stack and stack[-1] < i:
					stack.append(i)
				else:
					while stack and stack[-1] > i and (N > 0):
						stack.pop()
						N -= 1
					if i == '0':
						if stack:
							stack.append(i)
					else:
						stack.append(i)
			while stack and N:
				stack.pop()
				N -= 1
			return ''.join(stack) if stack else '0'
		return solve(S, N)


class Solution:

	def buildLowestNumber(self, S, N):
		s1 = []
		for i in S:
			while len(s1) > 0 and s1[-1] > i and (N > 0):
				N -= 1
				s1.pop()
			s1.append(i)
		while N > 0:
			s1.pop()
			N -= 1
		h = ''.join(s1)
		return int(h)


class Solution:

	def buildLowestNumber(self, S, N):
		s = []
		for x in S:
			while s and N and (s[-1] > x):
				s.pop()
				N -= 1
			s.append(x)
		while N:
			s.pop()
			N -= 1
		return int(''.join(s))


class Solution:

	def buildLowestNumber(self, S, N):
		n = len(S)
		mystack = []
		for c in S:
			while mystack and N > 0 and (mystack[-1] > c):
				N -= 1
				mystack.pop()
			if mystack or c != '0':
				mystack.append(c)
		while mystack and N:
			mystack.pop()
			N -= 1
		if mystack == []:
			return '0'
		return ''.join(mystack)


class Solution:

	def buildLowestNumber(self, s, k):
		l = []
		n = 0
		i = 1
		l.append(s[0])
		n += 1
		while i < len(s):
			while len(l) != 0 and l[len(l) - 1] > s[i] and (k > 0):
				l.pop()
				k -= 1
			l.append(s[i])
			i += 1
		while k > 0:
			l.pop()
			k -= 1
		r = ''
		while len(l) != 0:
			r += str(l.pop())
		k = 0
		r = r[::-1]
		for i in r:
			if i != '0':
				break
			else:
				k += 1
		if k == len(r):
			return '0'
		return r[k:]


class Solution:

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


from collections import deque

class Solution:

	def buildLowestNumber(self, S, N):
		stack = deque()
		if N == 0:
			return S
		i = 1
		stack.append(S[0])
		k = 0
		while len(stack) and k < N and (i < len(S)):
			while len(stack) and S[i] < stack[-1] and (k < N):
				stack.pop()
				k += 1
			stack.append(S[i])
			i += 1
		while i < len(S):
			stack.append(S[i])
			i += 1
		while k < N and len(stack):
			stack.pop()
			k += 1
		res = ''
		while len(stack):
			res = stack.pop() + res
		while res[0] == '0' and len(res) > 1:
			res = res[1:]
		return res


class Solution:

	def buildLowestNumber(self, s, k):
		stack = []
		for i in range(len(s)):
			if not stack:
				stack.append(s[i])
			else:
				while stack and stack[-1] > s[i]:
					if k >= 1:
						k -= 1
						stack.pop()
					else:
						break
				stack.append(s[i])
		res = ''
		while stack and k > 0:
			stack.pop()
			k -= 1
		for i in stack:
			res += i
		curr = ''
		for i in range(len(res)):
			if res[i] != '0':
				curr += res[i:]
				break
		if curr == '':
			return 0
		return curr


class Solution:

	def buildLowestNumber(self, s, n):
		sta = []
		for i in s:
			if len(sta) == 0:
				sta.append(i)
			else:
				while n > 0 and len(sta) > 0 and (sta[-1] > i):
					sta.pop()
					n -= 1
				sta.append(i)
		while n > 0 and len(sta) > 0:
			sta.pop()
		while len(sta) > 0 and sta[0] == '0':
			sta.remove(sta[0])
		if len(sta) == 0:
			sta = ['0']
		return ''.join(sta)


class Solution:

	def buildLowestNumber(self, S, N):
		ans = ''
		for i in S:
			while len(ans) > 0 and ans[-1] > i and (N > 0):
				ans = ans[:-1]
				N -= 1
			ans += i
		while N > 0 and len(ans) > 0:
			N -= 1
			ans = ans[:-1]
		return str(int(ans))


class Solution:

	def buildLowestNumber(self, s, k):
		stack = []
		for num in s:
			while stack and k and (int(stack[-1]) > int(num)):
				stack.pop()
				k -= 1
			stack.append(num)
		while k:
			stack.pop()
			k -= 1
		ans = ''.join(stack)
		ans = ans.lstrip('0')
		if ans:
			return ans
		return '0'


class Solution:

	def buildLowestNumber(self, nums, k):
		stack = [nums[0]]
		i = 1
		while i < len(nums):
			while stack and k > 0 and (stack[-1] > nums[i]):
				stack.pop()
				k -= 1
			stack.append(nums[i])
			i += 1
		return int(''.join(stack[:len(stack) - k]))


from collections import deque

class Solution:

	def buildLowestNumber(self, S, k):
		st = deque()
		for ch in S:
			while st and st[-1] > ch and k:
				k -= 1
				st.pop()
			st.append(ch)
		while st and k:
			st.pop()
			k -= 1
		while st and st[0] == '0':
			st.popleft()
		return ''.join(st) if st else '0'


class Solution:

	def buildLowestNumber(self, S, N):
		if N == len(S):
			return 0
		if len(set(S)) == 1:
			return S[:-N]
		ans = []
		for i in S:
			while ans and ans[-1] > i and (N > 0):
				ans.pop()
				N -= 1
			ans.append(i)
		while N > 0:
			ans.pop()
			N -= 1
		a = ''.join(ans)
		return int(a)


class Solution:

	def buildLowestNumber(self, S, N):
		if N == len(S):
			return 0
		if len(set(S)) == 1:
			return S[:-N]
		x = []
		x.append(S[0])
		for i in S[1:]:
			while len(x) > 0 and N > 0 and (x[-1] > i):
				x.pop()
				N -= 1
			x.append(i)
		while N > 0:
			x.pop()
			N -= 1
		z = ''.join(x)
		return int(z)


class Solution:

	def buildLowestNumber(self, S, N):
		l = []
		for i in S:
			n = int(i)
			while l and N > 0 and (n < l[-1]):
				l.pop()
				N -= 1
			l.append(n)
		while l and N > 0:
			l.pop()
			N -= 1
		t = [str(i) for i in l]
		return str(int(''.join(t)))


class Solution:

	def buildLowestNumber(self, S, N):
		i = 1
		while N > 0 and len(S) > 0:
			if i != len(S) and S[i] >= S[i - 1]:
				i += 1
			else:
				S = S[:i - 1] + S[i:]
				i -= 1
				if i == 0:
					i = 1
				N -= 1
		i = 0
		while i < len(S) - 1 and int(S[i]) == 0:
			i += 1
		return S[i:]


class Solution:

	def buildLowestNumber(self, S, N):
		stack = []
		for num in S:
			while N and stack and (stack[-1] > num):
				stack.pop()
				N -= 1
			stack.append(num)
		final = ''.join(stack[:len(stack) - N]).lstrip('0')
		return '0' if not final else final


class Solution:

	def buildLowestNumber(self, S, k):
		stri = []
		for num in S:
			while stri and k and (int(stri[-1]) > int(num)):
				stri.pop()
				k -= 1
			stri.append(num)
		while k:
			stri.pop()
			k -= 1
		ans = ''.join(stri)
		ans = ans.lstrip('0')
		return ans if ans else '0'