Case study: remove k digits - using stack linear time complexity

Dec 31, 2019

Case study

	def removeKdigits(num: str, k: int) -> str:
	# if len(num) <= k:
	# return 0
	# digits = list(map(int, num))
	# for i in range(k):
	# removed = False
	# for j in range(len(digits) - 1): # j - start from 0
	# if digits[j] > digits[j + 1]:
	# digits.remove(digits[j])
	# removed = True
	# break
	# if not removed:
	# digits.pop() # ? remove last digit in original
	# return ''.join(list(map(str, digits)))
	if len(num) <= k:
	return '0'
	stack = []
	for digit in num:
	while k and stack and int(stack[-1]) > int(digit):
	stack.pop()
	k -= 1
	stack.append(digit)
	for i in range(k):
	stack.pop()
	return str(int(''.join(stack)))
	print(removeKdigits("1432219", 3)) # 9 54351, 31
	print(removeKdigits("10200", 1))
	print(removeKdigits("10", 2))

view raw removeKDigits.py hosted with ❤ by GitHub