Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

The explanation is here https://www.youtube.com/watch?v=3QJzHqNAEXs

class Stack<T> {
	var array:[T] = [T]()
	func push(_ item: T) {
		array.append(item)
	}
	func pop() -> T {
		return array.removeLast()
	}
	func isEmpty() -> Bool {
		return array.isEmpty
	}
	func top() -> T? {
		return array.last
	}
	func display() -> [T] {
		print(array)
		return array
	}
}

class SmallestInteger {
	static func removeKdigits(_ num: String, _ k: Int) -> String {
		var kNumbersToRemove = k
		let stack:Stack<Int> = Stack<Int>()
		var numbers:[Int] = num.compactMap { char in
			char.wholeNumberValue
		}
		for number in numbers {
			while (!stack.isEmpty() && kNumbersToRemove > 0 && stack.top()! > number) {
				stack.pop()
				kNumbersToRemove -= 1
			}
			if !stack.isEmpty() || number != 0 {
				stack.push(number)
			}
		}
                // this logic is to handle numbers like 1001, k=2 
		while !stack.isEmpty() && kNumbersToRemove > 0 {
			kNumbersToRemove -= 1
			stack.pop()
		}
		if stack.isEmpty() {
			return "0"
		}
			
		var stringArray = stack.display().map { number in
			String(number)
		}
		return stringArray.joined()
	}
}
print(SmallestInteger.removeKdigits("1432219", 3))

We use a stack here to store the values. If the previous number is greater than the current number, we will remove the previous number. Else store the number in the stack.

Leave a Reply

Your email address will not be published. Required fields are marked *