A greedy method using stack, O(n) time and O(n) space


  • 68
    K
    public class Solution {
        public String removeKdigits(String num, int k) {
            int digits = num.length() - k;
            char[] stk = new char[num.length()];
            int top = 0;
            // k keeps track of how many characters we can remove
            // if the previous character in stk is larger than the current one
            // then removing it will get a smaller number
            // but we can only do so when k is larger than 0
            for (int i = 0; i < num.length(); ++i) {
                char c = num.charAt(i);
                while (top > 0 && stk[top-1] > c && k > 0) {
                    top -= 1;
                    k -= 1;
                }
                stk[top++] = c;
            }
            // find the index of first non-zero digit
            int idx = 0;
            while (idx < digits && stk[idx] == '0') idx++;
            return idx == digits? "0": new String(stk, idx, digits - idx);
        }
    }
    

  • 0
    J

    How could you deal with this case ('553', 2) or ('123', 2')?


  • 3
    F

    @JoeX.TJUF

    The variable digits ensures the extra ending values would not be included in the final result.

    Consider "123", 1, then digits == 2, so that in the end stk == ['1', '2', '3'], but the result is the first digits values in the stk, i.e. "12", instead of "123".


  • 1
    I

    My solution beats 100%, the main idea is same with others, an optimized part is when k == 0, just copy the left part to newContent and avoid other operation.

        public String removeKdigits(String num, int k) {
            // simple case pass
            if (k == 0) {
                return num;
            }
            int len = num.length();
            if (k == len) {
                return "0";
            }
            
            char[] content = num.toCharArray();
            // newContent store the result
            char[] newContent = new char[len];
    
            newContent[0] = content[0];
            // newIndex points to the next value to be filled in(which means newIndex - 1 is the last value)
            int newIndex = 1;
            for (int i = 1; i <= len - 1; i++) {
                char ch = content[i];
                // replace the old value that smaller than ch
                while (k > 0 && newIndex >= 1 && ch < newContent[newIndex - 1]) {
                    newIndex--;
                    k--;
                }
                // place ch
                newContent[newIndex] = ch;
                newIndex++;
                // if k is 0, copy the rest to the newContent, the size of rest is (len - 1 - i + 1)
                if (k == 0) {
                    i++;
                    System.arraycopy(content, i, newContent, newIndex, len - i);
                    newIndex += (len - i);
                    break;
                }
                
            }
            // remove head '0'
            int startIndex = 0;
            while (newContent[startIndex] == '0') {
                startIndex++;
            }
            if (newIndex - startIndex - k == 0) {
                return "0";
            }
            return new String(newContent, startIndex, newIndex - startIndex - k);
        }
    

  • 0
    H

    @JoeX.TJUF the case ("553",2) would give stk=['3','5'], result ="3". The case("123",2) would give stk['1','2','3'], result="1".

    The whole idea of this method is to make small number move forward by at most k digits and output a number of length num.length-k.

    So ("553",2) would make 3 move 2 digits forward, ending to ['3','5'].
    ("123",2) would not change, ending to ['1','2','3'].
    Then select the small number from the beginning of num.length-k.


  • 0

    very nice, same idea here in C#

        public string RemoveKdigits(string num, int k)
        {
            int len = num.Length;
            Stack<int> stack = new Stack<int>();
            
            for (int i = 0; i < len; i++)
            {
                while (k > 0 && stack.Count > 0 && num[stack.Peek()] > num[i])
                {
                    stack.Pop();
                    k--;
                }
                stack.Push(i);
            }
            
            StringBuilder sb = new StringBuilder();
            while (stack.Count > 0)
            {
                sb.Append(num[stack.Pop()]);
                if (k-- > 0) sb.Length--;
            }
            
            StringBuilder output = new StringBuilder();
            for (int i = sb.Length - 1; i >= 0; i--)
            {
                if (output.Length > 0 || sb[i] != '0') output.Append(sb[i]);
            }
            
            return output.Length > 0 ? output.ToString() : "0";
        }
    

  • 1

    from left to right of the string, put each of char into a new stringbuilder instance.
    when k > 0, check these chars in the new stringbuilder result from right to left, which one is smaller, keep smaller one.

    Input: num = "1432219", k = 3
    
    For example, now in stringbuilder is 14. We check '3', 3 is smaller than 4, remove 4, append 3.
    now stringbuilder is 13, we check '2', 2 is smaller than 3, remove 3, append 2.
    now stringbuilder is 12, we check '2', 2 is equal to 2, append 2.
    now stringbuilder is 122, we check `1`, 1 is smaller than 2, remove 2, append 1.
    now stringbuilder is 121, now k is 0, we append 9.
    
    Output: "1219"
    
      public String removeKdigits(String num, int k) {
        char[] sc = num.toCharArray();
        if(k >= sc.length) return "0";
        StringBuilder sb = new StringBuilder();
        for(char c: sc){
          while(sb.length() > 0 && sb.charAt(sb.length() - 1) > c && k > 0){
            sb.deleteCharAt(sb.length() - 1);
            k--;
          }
          sb.append(c);
        }
    
    // handle case like "0200"
        while(sb.length() > 1 && sb.charAt(0) == '0'){
          sb.deleteCharAt(0);    
        }
    
    //handle case like "112", k = 1
        for(int i=0; i < k; i++){
          sb.deleteCharAt(sb.length() - 1);    
        }
        return sb.toString();
      }
    ``

  • 0
    O

    num = "99991"
    k = 4

    your programe answer is 9
    it's wrong~~
    if we have a
    top--;
    we need to check
    top-1 with top-2


  • 0
    O

    sorry you are right


  • 0
    public String removeKdigits(String num, int k) {
        StringBuilder res = new StringBuilder();
        for (int i=0; i<num.length(); i++) {
            while (res.length()>0 && res.charAt(res.length()-1)>num.charAt(i) && k-->0) res.deleteCharAt(res.length()-1);
            res.append(num.charAt(i));
        }    
        if(k>0) res.delete(res.length()-k, res.length()); 
        // trim leading zeros
        int s = -1; 
        while (++s<res.length()&&res.charAt(s)=='0');
        String result = res.substring(s, res.length());
        return result.equals("") ? "0" : result;
    }

  • 0
    A

    Thanks for sharing such nice solution. Here is a Java update one with O(n - k) space.

    class Solution {
        public String removeKdigits(String num, int k) {
            if (num.length() <= k) return "0";
            
            int digits = num.length() - k;
            char[] stk = new char[digits];
            int top = 0;
            
            for (int i = 0; i < num.length(); i++) {
                char c = num.charAt(i);
                while (top > 0 && stk[top - 1] > c && k > 0) {
                    k--;
                    top--;
                }
    
                if (top < digits) {
                    stk[top++] = c;
                } else { 
                    /**
                     * current digit is greater than prev one
                     * and top has reach the last pos of stk
                     * then ignor current digit (delete it)
                     */
                    k--;
                }
            }
    
            int idx = 0;
            while (idx < digits && stk[idx] == '0') idx++;
            return idx == digits ? "0" : new String(stk, idx, digits - idx);
        }
    }
    

  • 0
    I

    Thanks a lot, I implement this idea with c++

    class Solution {
    public:
        string removeKdigits(string num, int k) {
    		int digitsCnt = num.size() - k;
    		vector<char> stack;
    		
    		// push to stack, compare and remove.
    		if (num.empty())
    			return string("0");
    		stack.push_back(num[0]);
    		for (unsigned i = 1; i < num.size(); i++)		
    		{
    			char c = stack.back();
    			while (num[i] < c && k > 0)
    			{
    				stack.pop_back();
    				k--;
    				// if stack is empty, out while loop
    				if(stack.empty())
    					break;
    				else
    					c = stack.back();
    			}
    			stack.push_back(num[i]);
    		}
    
    		// pick first digitsCnt digits from bottom to up of the stack
    		vector<char> digits(stack.begin(), stack.begin() + digitsCnt);
    		unsigned j = 0;
    		while (!digits.empty() && digits[j] == '0')	// skip leading zero
    			++j;
    
    		// construct result
    		string result(digits.begin() + j, digits.end());
    		if (result.empty())
    			return string("0");
    		return result;
        }
    };
    

  • 0
    E

    Another solution:

    string removeKdigits(string num, int k) {
        if(k>=num.size())return "0";
        string res(1,num[0]);
        int i=1;
        while(k>0){
            if(i==num.size()||res.back()>num[i]){res.pop_back();k--;}
            else{
                if(res!=""||num[i]!='0')res+=num[i];
                i++;
            }
        }
        for(;i<num.size();i++)if(res!=""||num[i]!='0')res+=num[i];
        return res==""?"0":res;
    }
    

    For more, there is a way to promote this solution, if k<len(num)/2, remove k digits; Else, select len(num)/2-k digits. Such promotion can make Tn=O(n/2)


  • 0
    D

    @keyulai92gmail.com Could you explain this: new String(stk, idx, digits - idx).
    I still cannot get it.Thanks1


Log in to reply
 

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