Java solution using stack and regex, O(n)


  • 0
    L

    The idea is that, we iterate through every character in num and pushing it into a stack. Every time before we push, we compare it to the peek() of the stack, and if the current character is less than the peek character in the stack, we pop the peek character from stack.

    After an O(n) iteration, all the remaining characters are in the stack, and we pop them out one by one (from bottom to top). Also, we need to get rid of the preceding zeros.

     public String removeKdigits(String num, int k) {
            if(k == 0) return num; 
            Deque<Character> stack = new ArrayDeque();
            int count = 0;
            for(int i=0; i<num.length(); i++){
                char c = num.charAt(i);
                while(count < k && !stack.isEmpty() && c < stack.peek()){
                        stack.pop(); 
                        count++;
                }
                stack.push(c);
            }
            while(count++ < k) stack.pop();
            StringBuilder sb = new StringBuilder();
            while(!stack.isEmpty()){
                sb.append(stack.pollLast());
            }
            String rlt = removeZero(sb.toString());
            return rlt.length() == 0?"0":rlt;
        }
        
     public String removeZero(String str){
            return str.replaceFirst("^0+","");      //remove preceding 0s
     }
    

Log in to reply
 

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