c++ easy O(n) runtime and O(1) space solution - greedy


  • 0
    B

    Instead of thinking what to remove, we can think what to pick as a typical way to simplify greedy/dp programs.

    Input: num = "1432219", k = 3, we know we need to pick 3 numbers
    the first number to pick has to be between num[0] ~ num[num.size() - 2]
    the second number to pick has to be between num[i_firstpick + 1] ~ num[num.size() - 1]
    the last number to pick has to be between num[i_secondpick + 1] ~ num[num.size()]

    we can observe the min digit (m) of each pick will result in global optimal solution, because had we picked another digit lets say x, where x > m we know that the solution then smallest possible is going to be x00 which is still larger than m99.

    runtime is O(n) since we have to look at each digit exactly once

    string removeKdigits(string num, int k) {
        size_t szNum = num.size();
        size_t kRem = szNum - k;
        string res;
        auto it = num.begin();
        while (kRem-- > 0) {
            auto itMin = min_element(it, num.end() - kRem);
            res.push_back(*itMin);
            it = itMin + 1;
        }
    
        auto notzero = res.find_first_not_of('0');
        res = res.erase(0, notzero);
        if (res.empty()) return "0";
        return res;
    }
    

Log in to reply
 

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