O(string length + k) solution in c++


  • 0

    You need to remove the first negative slope like (cur_digit > next_digit)
    i.e cur num is greater than next num;
    Initialize next to 0, to take care of the corner case i.e when we have the units place as highest.

    Once you find the above case, remove that make the index (cur -1), decrement k and continue checking.
    In the end find first not of '0' and erase the string until that.
    Incase string is empty put a 0;
    This will result in a single iteration of the string i.e O(sting length + k)
    Initialize next to 0, to take care of the corner case i.e when we have the units place as highest.

    class Solution {
    public:
        string removeKdigits(string num, int k) {
            int i = 0;
            while(k)
            {
                int cur=0,next=0;
                
                if(num[i] != 0)    
                    cur = num[i] - '0';
                    
                if(i < (num.size()-1))
                    next = num[i+1] - '0';
                
                if((cur > next) || (k == (num.size()-i)))
                {
                    num.erase(i,1);
                    i = max(-1,i-2);
                    k--;
                }
                i++;
            }
            
            std::size_t found = num.find_first_not_of("0");
            num.erase(0,found);
            
            if(num.size() == 0)
                num.push_back('0');
                
            return num;
        }
    };
    

Log in to reply
 

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