Remove K Digits

 

 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"

Input: num = "10200", k = 1
Output: "200"

Input: num = "10", k = 2
Output: "0" 

 

 class Solution {
public:
    string removeKdigits(string num, int k) {
        int i=0;
        if(num.size()==1&&num[0]>='0'&&num[0]<='9'&&k>=1)return "0";
        while(i<num.size()-1&&k>0)
        {
            if(num[i]>num[i+1])
            {
                num.erase(i,1);
                --k;
            if(i-1>=0&&num[i-1]>num[i])
                     --i;
            }else{
                ++i;
            }
        }
        while(i>0&&k>0){
           if(num[i]>=num[i-1])
           {
               num.erase(i,1);
               --k;
            }
            --i;
        }
        i=0;
        while(k>0&&i<num.size())
        {
            num.erase(i,1);
            --k,++i;
        }
        i=0;
        while(num[i]=='0'){
            num.erase(i,1);}
        if(num.empty())return "0";
        return num;
        
    }
};

 

--------------------------------------------------------------------------------------------------------------------------------------

class Solution {
public:
    string removeKdigits(string num, int k) {
       string ans="";
        for(auto ch : num)
        {
            while(k!=0 &&ans.size()>0&&ans.back()>ch)
            {
                ans.pop_back();
                --k;
            }
           
            if(ch=='0'&&ans.size()==0)
                continue;
           
            ans.push_back(ch);
           
        }
        while(ans.size()>0&&k>0)
        {
            ans.pop_back();
            --k;
        }
        if(ans.empty())return "0";
        return ans;
       
    }
};