Description (leetcode)

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

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.

Constraints:

  • 1 <= k <= num.length <= 10^5
  • num consists of only digits.
  • num does not have any leading zeros except for the zero itself.

submission

impl Solution {
    pub fn remove_kdigits(num: String, mut k: i32) -> String {
        let mut stack = Vec::with_capacity(num.len());
        // insert a leading zero here to save us from check emptiness later
        stack.push('0');
        for d in num.chars() {
            while k > 0 && stack.last().is_some_and(|&v| v > d) {
                k -= 1;
                stack.pop();
            }
            stack.push(d);
        }
        // we need to removed enough digit
        for _ in 0..k {
            stack.pop();
        }
        // pop a digit so we would not remove the only digit 0
        let last = stack.pop();
        stack
            .into_iter()
            .skip_while(|&c| c == '0') // remove leading zeroes
            .chain(last) // chain the pop'ed digit back
            .collect::<String>()
    }
}