# Annotated greedy C+ solution

• ``````string removeKdigits(string num, int k) {
// the reasoning on weather the greedy solution works starts with an
//  observation that removing _a_ vs. removing _b_ in the number
//  "[.1.]a[.2.]b[.3.]" doesn't change blocks "[.1.]" and "[.3.]"
// therefore the choice between eliminating _a_ vs. _b_ is made based
//  on comparison of "[.2.]b" with "a[.2.]" or, equivalently, digit
//  _a_ and the following digit from block "[.2.]" (consider no ties)
// in other words we need to scan the _num_ from the most significant
//  (left-most) side looking for sequential pairs _ab_ where _a_>_b_
//  and drop _a_ until we exhaust _k_

// check the trivial cases first
if( num.size() <= k ) return "0";
if( k <= 0 ) return num;

// look for the first left-most case of decreasing _ab_ sequence
for(int pos=0; pos<num.size()-1 && k>0; ){
if( num[pos] > num[pos+1] ){
num.erase(pos,1);
pos = 0; // start over for simplicity
k--;
} else
pos++;
}

// still need to delete something? chop "biggest" digits from the tail
num.erase( num.size()-k, k );

// drop leading zeros
int pos = 0;
for(; pos<num.size() && num[pos] == '0'; pos++);
if( pos ) num.erase(0,pos);

// yet another trivial case
if( num.size() == 0 ) return "0";

return num;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.