C++ Naive Solution - 3ms


  • 0
    P

    There are two rules to generate the smallest substring after removing k digits:

    1. If the length of substring with non-zero digits at the head is no more than k, we should remove them first. Because the sequential zeros will bring us extra digit decreasing.
    2. For the rest string after executing Rule. 1, we just should find the first digital of the first descending interval from left to right. Thus we could guarantee that the most significant digit will be removed.
    class Solution {
        public:
        ///@brief   given a string assembled with numbers, removing k digit makes it became the smallest number in those digits
        string removeKdigits(string num, int k) {
            int len = num.length();
            if (k >= len)   return "0";
            
            int  nz = countLeadingNonZero(num); // the counter of the non-zero digits
            while (nz <= k) {
                k -= nz;
                int z = nz; //  the counter of the sequential zero digits
                while (z < len && num[z] == '0')   z++;
                
                if (z == len)   return "0";
                
                num = num.substr(z, len - z);
                len = num.length();
                nz = countLeadingNonZero(num);
            }
            
            while (k > 0) {
                for (int i = 0; i < num.length() - 1; i++) {
                    if (num[i] > num[i + 1]) {
                        num.erase(i, 1);
                        break;
                    }
                    //  if the digits are ordered in non-descending order, we just remove the last digit
                    if (i == num.length() - 2) {
                        if (num[i] <= num[i + 1])
                            num.pop_back();
                    }
                }
                k--;
            }
            return num;
        }
        
        ///@brief   count the leading non-zero digits before the first zero digit in string s
        int countLeadingNonZero(string s) {
            if (s.empty())  return 0;
            int cnt = 0;
            while (cnt < s.length() && s[cnt] != '0') {
                cnt++;
            }
            return cnt;
        }
    };
    

Log in to reply
 

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