402. Remove K Digits

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.

Rust Solution

struct Solution;

impl Solution {
    fn remove_kdigits(num: String, mut k: i32) -> String {
        let mut stack: Vec<char> = vec![];
        for c in num.chars() {
            while let Some(&top) = stack.last() {
                if k > 0 && top > c {
                    stack.pop();
                    k -= 1;
                } else {
                    break;
                }
            }
            stack.push(c);
        }
        while k != 0 {
            stack.pop();
            k -= 1;
        }

        let res: String = stack.into_iter().skip_while(|&c| c == '0').collect();
        if res.is_empty() {
            "0".to_string()
        } else {
            res
        }
    }
}

#[test]
fn test() {
    let num = "1432219".to_string();
    let k = 3;
    let res = "1219".to_string();
    assert_eq!(Solution::remove_kdigits(num, k), res);
    let num = "10200".to_string();
    let k = 1;
    let res = "200".to_string();
    assert_eq!(Solution::remove_kdigits(num, k), res);
    let num = "10".to_string();
    let k = 2;
    let res = "0".to_string();
    assert_eq!(Solution::remove_kdigits(num, k), res);
}

Having problems with this solution? Click here to submit an issue on github.