Description
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
Input: num = "1432219", k = 3, Output: "1219"
Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Input: num = "10200", k = 1, Output: "200"
Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Input: num = "10", k = 2, Output: "0"
Remove all the digits from the number and it is left with nothing which is 0.
Idea
Greedy algorithm works in this case. Suppose x > y, and we want to remove one digit from x, then we can move the same digit in y, and get x' >= y'. Hence, it never hurts to remove one digit which make the number smallest.
To remove a single digit to make the remaining number smallest, we remove the first digit, whose right neighbor is strictly smaller than itself.
Solution
class Solution {
private:
string removeOneDigit(string num) {
int index = 0;
while (index < num.size() - 1 && num[index + 1] >= num[index]) {
index++;
}
return num.substr(0, index) + num.substr(index + 1);
}
public:
string removeKdigits(string num, int k) {
for (int i = 0; i < k; i++) {
num = removeOneDigit(num);
}
int index = 0;
while (index < num.size() && num[index] == '0') index++;
num = num.substr(index);
if (num.empty()) num = "0";
return num;
}
};
Performance
33 / 33 test cases passed.
Runtime: 16 ms
