Java O(n) solution


  • 0
    U
    public String removeKdigits(String num, int k) {
        
        int len = num.length() - k;
        char[] res = new char[len];
        
        for(int i = 0, index = 0; i < num.length(); i++){
            while(index > 0 && len - index < num.length() - i && num.charAt(i) < res[index-1]){
                index--;
            }
            if(index < len){
                res[index++] = num.charAt(i);
            }
        }
        
        int idx = 0;
        while (idx < len && res[idx] == '0'){
            idx++;
        }
        return idx == len? "0": new String(res, idx, len - idx);
    }

Log in to reply
 

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