402. Remove K Digits

Problem

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.

Problem Summary

Given a non-negative integer num represented as a string, remove k digits from this number so that the remaining number is the smallest possible.

Note:

• The length of num is less than 10002 and ≥ k.
• num will not contain any leading zeros.

Solution Approach

Scan each digit of num from the beginning and push them onto a stack in order. When the new digit is smaller than the top element of the stack, keep moving backward and remove all digits that are larger than this new digit. Note that the final requirement is to make the remaining number as small as possible. If the remaining number has more than K digits at the end, taking the first K digits must be the smallest (because if the last K digits contained values smaller than the first K digits, the larger digits in front would have been removed).

Note that although num does not contain leading 0s, after deleting digits in the middle, for example after deleting all digits before a 0, leading 0s may appear. They should be removed when producing the final output.

Code

package leetcode

func removeKdigits(num string, k int) string {
	if k == len(num) {
		return "0"
	}
	res := []byte{}
	for i := 0; i < len(num); i++ {
		c := num[i]
		for k > 0 && len(res) > 0 && c < res[len(res)-1] {
			res = res[:len(res)-1]
			k--
		}
		res = append(res, c)
	}
	res = res[:len(res)-k]

	// trim leading zeros
	for len(res) > 1 && res[0] == '0' {
		res = res[1:]
	}
	return string(res)
}