Super simple recursive method.

  • 0

    The idea is: the first letter of the answer can only be chosen from the first k+1 letters, otherwise the rest is not enough for n-k letters. Then choose the smallest one from the first k+1 letters. Do it recursively

        string removeKdigits(string num, int k) {
            string ans = helper(num, k);
            while (ans.size() > 0 && ans[0] == '0') ans.erase(ans.begin());
            return ans.size() == 0 ? "0" : ans;
        string helper(string num, int k) {
            if (k <= 0) return num;
            if (k >= num.size()) return "";
            int j = min_element(num.begin(), num.begin()+k+1) - num.begin();
            return num.substr(j,1) + helper(num.substr(j+1), k-j);

Log in to reply

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