C++ 6ms 10 lines solution with comments


  • 6
    string removeKdigits(string num, int k) {
           string ans = "";                                         // treat ans as a stack in below for loop
           
           for (char c : num) {
               while (ans.length() && ans.back() > c && k) {
                   ans.pop_back();                                  // make sure digits in ans are in ascending order
                   k--;                                             // remove one char
               }
               
               if (ans.length() || c != '0') { ans.push_back(c); }  // can't have leading '0'
           }
           
           while (ans.length() && k--) { ans.pop_back(); }          // make sure remove k digits in total
           
           return ans.empty() ? "0" : ans;
    }
    

  • 0
    D

    I think the second comment should be "increasing sequence" rather than "decreasing sequence".


  • 0

    @danisein
    Good catch! I've fixed it. Thanks.


  • 0
    Q

    I ran your code and it is only 3 ms. Amazing.


  • 3
    K

    Hey @soamaaazing ,

    your idea can be done inplace.

    class Solution {
    public:
        string removeKdigits(string s, int k) {
           int sz = 0;
           for (size_t i = 0; i < s.size(); ++i) {
               char c = s[i];
               while (sz > 0 && s[sz-1] > c && k > 0) {
                   --sz;
                   --k;
               }
               if (sz > 0 || c != '0') s[sz++] = c;
           }
           sz = max(sz - k, 0);
           s.resize(sz);
           return sz == 0 ? "0" : s;
        }
    };
    

  • 0

    @K0stIa
    Good suggestion, your code absolutely works. Thanks!


  • 0
    Z

    @soamaaazing
    Could you explain a little more on the resize part?
    Is it guaranteed that the last k element will be dropped?


  • 0

    @zhengpenghu
    If you look at my original post, you'll find ans with length of num.length() - k.
    The resize solution is doing exactly the same thing except that it's using s's prefix as ans in my original solution, which is doing it "in place".
    Given above, it's clear that s will end up with my ans as its prefix, which is of length num.length() - k. So it is guaranteed that the last k element will be dropped


Log in to reply
 

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