share 5ms solution beats 98.22% with adequate comments


  • 0
    I

    The key idea is to avoid String.subString() + String.subString()

    public class Solution {
        public String removeKdigits(String num, int k) {
            final char[] nums = num.toCharArray();
            int x = 0;
            for(int i=0; i<k; i++) {
                if(x >= nums.length - 1) {
                    x++;
                    break;
                }
                
                if(nums[x+1] == '0'){
                    //next is zero, let's also remove all possible zeros
                    x = x+2;
                    while(x < nums.length && nums[x] == '0') {
                        x++;
                    }
                }else if(nums[x] > nums[x+1]) {
                    //next is not zero and is smaller than current, happy path
                    x++;
                }else {
                    //next is not zero, and is greater than or equal to current
                    //let's find the largetest possible digit to remove
                    //e.g. "2231" should remove '3'
                    int y = x+1;
                    while(y < nums.length-1 && nums[y] <= nums[y+1]) {
                        y++;
                    }
                    //in the simple case, this array copy is idential to nums[x+1] = nums[x]
                    System.arraycopy(nums, x, nums, x+1, y-x);
                    x++;
                }
            }
            
            return nums.length > x ? new String(nums, x, nums.length - x) : "0";
        }
    }
    

Log in to reply
 

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