# C++ Naive Solution - 3ms

• There are two rules to generate the smallest substring after removing k digits:

1. If the length of substring with non-zero digits at the head is no more than k, we should remove them first. Because the sequential zeros will bring us extra digit decreasing.
2. For the rest string after executing Rule. 1, we just should find the first digital of the first descending interval from left to right. Thus we could guarantee that the most significant digit will be removed.
``````class Solution {
public:
///@brief   given a string assembled with numbers, removing k digit makes it became the smallest number in those digits
string removeKdigits(string num, int k) {
int len = num.length();
if (k >= len)   return "0";

int  nz = countLeadingNonZero(num); // the counter of the non-zero digits
while (nz <= k) {
k -= nz;
int z = nz; //  the counter of the sequential zero digits
while (z < len && num[z] == '0')   z++;

if (z == len)   return "0";

num = num.substr(z, len - z);
len = num.length();
}

while (k > 0) {
for (int i = 0; i < num.length() - 1; i++) {
if (num[i] > num[i + 1]) {
num.erase(i, 1);
break;
}
//  if the digits are ordered in non-descending order, we just remove the last digit
if (i == num.length() - 2) {
if (num[i] <= num[i + 1])
num.pop_back();
}
}
k--;
}
return num;
}

///@brief   count the leading non-zero digits before the first zero digit in string s