Problem overview
The function remove_kdigits receives a string num of digits and an integer k. It must remove exactly k digits so that the number left is as small as possible, and return it as a string with no leading zeros. If nothing is left, or only zeros, the answer is "0".
For num = "1432219" and k = 3 the answer is "1219": removing 4, 3 and 2 leaves 1219. For "10200" and k = 1, removing the 1 leaves 0200, which is written "200". For "10" and k = 2 every digit goes, so the answer is "0".
Approach: drop a digit that is bigger than its right neighbour
Trying every way of choosing k digits to remove is hopeless for a string of up to 100,000 digits. A greedy rule is enough. All kept numbers have the same length, so they compare from the left: the leftmost digit matters most.
Now look at two neighbouring digits where the left one is bigger, as in 43. Removing the 4 puts the smaller 3 into its place, and the number gets smaller. Removing any digit further right would leave that 4 in a more significant position. So whenever a digit is bigger than the one after it, removing it is the best move.
A stack applies this rule in one pass. Scan the digits left to right, keeping the digits you plan to keep. Before pushing a digit c, pop every digit on top that is bigger than c, as long as removals remain. Then push c. The stack always holds a number that never decreases from the bottom to the top, unless the removals ran out.
If the scan ends with removals left over, the digits never went down, as in 1234. The stack then rises from bottom to top, so its biggest digits are on top, and the best digits to remove are the last ones.
Finally, leading zeros are skipped when writing the answer out, and an empty result becomes "0".
Step by step
- Create the stack as a
Vec<char>.pushandpopwork at its end, which is the top. - Loop over
num.chars()with the variablec. Each digit is pushed once and popped at most once. - Pop bigger digits. The inner
whileruns whilek > 0, the stack is non-empty and the top digit is greater thanc. The emptiness test comes before the call tounwrap, so it can't fail. - Pop and count. Each pop uses one removal, so
kgoes down by one. - Push
c. It stays for now, because a smaller digit further right may still pop it. - Use up leftover removals. After the scan, while
k > 0, pop the top digit. - Hand the stack to a helper,
join_without_leading_zeros, which writes the digits out. - Skip leading zeros. The helper keeps a flag,
starting_zeros, that turns false at the first digit that isn't'0'. Digits are appended once the flag is false, so zeros after the first real digit, like those in 200, are kept. - Return
"0"for an empty result. The result is empty when nothing but zeros was left.
The solution in Rust
impl Solution {
fn remove_kdigits(num: String, mut k: i32) -> String {
let mut stack: Vec<char> = Vec::new();
for c in num.chars() {
while k > 0 && !stack.is_empty() && *stack.last().unwrap() > c {
stack.pop();
k -= 1;
}
stack.push(c);
}
while k > 0 {
stack.pop();
k -= 1;
}
Self::join_without_leading_zeros(&stack)
}
fn join_without_leading_zeros(stack: &[char]) -> String {
let mut starting_zeros = true;
let mut result = String::new();
for &ch in stack {
if ch != '0' {
starting_zeros = false;
}
if !starting_zeros {
result.push(ch);
}
}
if result.is_empty() {
"0".to_string()
} else {
result
}
}
}
The Rust details worth a look:
mut k: i32in the signature makes the parameter itself mutable, so the function can count it down without a second variable.*stack.last().unwrap().last()returns anOption<&char>,Nonefor an empty vector.unwrap()takes the reference out, and*reads thecharbehind it. The check!stack.is_empty()sits before it in the condition, and&&stops evaluating at the first false operand, sounwrap()never seesNone.- Comparing digit characters.
charvalues compare by code point, and'0'to'9'are consecutive, so'9' > '1'is true, just like the digits they show. A comparison of whole strings would not do this:"10" < "9"is true because strings compare character by character. num.chars()yields characters, not bytes. The input is only digits, so each character is one byte, butchars()is the right habit for text.&stackbecomes&[char]. The helper takes a slice, and Rust converts a reference to aVec<char>into one automatically.for &ch in stackiterates over&charitems. The pattern&chcopies eachcharout, sochcompares directly with'0'.- The final
if/elseis an expression, so there are no semicolons and noreturn. Both branches are aString:to_string()turns the literal"0"into one.
Complexity
Time: O(n). Each digit is pushed once and popped at most once, across both loops. The helper makes one more pass over the stack.
Space: O(n). The stack can hold every digit, and the result string is about as long.
Edge cases and common mistakes
- Removing everything.
"10"withk = 2pops both digits, the helper builds an empty string, and the function returns"0". Without the final check it would return an empty string. - Leading zeros after removal.
"10200"withk = 1leaves the stack0, 2, 0, 0. The helper skips the first zero and keeps the other two, giving"200". Dropping every zero would give"2". - Zeros only.
"100"withk = 1pops the 1 and then the stack is0, 0, which becomes"0". - Increasing digits.
"1234"withk = 2pops nothing in the scan. The second loop removes the last two digits, giving"12". Without it, the result would keep too many digits. - Equal digits.
"112"withk = 1pops nothing, because the comparison is strict. The second loop removes the 2, and the answer is"11". - Decreasing digits.
"54321"withk = 2pops 5 and 4, leaving"321". - Converting to a number. With up to 100,000 digits the value doesn't fit in any integer type, so the answer stays a string.
Testing
num = "1432219",k = 3gives"1219".num = "10200",k = 1gives"200".num = "10",k = 2gives"0".num = "1234",k = 2gives"12".num = "9",k = 1gives"0".
