Lengthy but easy to understand solution


  • 1
    A
    public class Solution {
        public String removeKdigits(String num, int k) {
            Objects.requireNonNull(num);
    
            if(k==0)return num;
            if(num.length()==1 && k==1)return "0";
            int pre=0,cur=1;
            StringBuilder sb = new StringBuilder(num);
            //from left to right, delete character that is bigger than right neighbor
            while(k>0 && cur<sb.length()){
                if(sb.charAt(cur)<sb.charAt(pre)){
                    sb.deleteCharAt(pre);
                    if(pre>0){
                    	//we now need to compare the left and right neighbors of the one being removed
                    	pre--;
                    	cur--;
                    }
    
                    k--;
                }else{
                	//moving forward if element in cur is greater than element at pre cursor
    	            pre=cur;
    	            cur++;
                }
            }
            //last pass might not remove enough characters
            int rightPosition = sb.length()-1;
          //then need to go through it from right to left and remove the right most non-zero one
            while(k>0 && rightPosition>=0){
            	if(sb.charAt(rightPosition)!='0'){
    	            sb.deleteCharAt(rightPosition);
    	            k--;
            	}
                rightPosition--;
            }
            //remove leading 0s
            while(sb.length()>0 && sb.charAt(0)=='0'){
            	sb.deleteCharAt(0);
            }
            return (sb.length()==0?"0":sb.toString());
        }
    }
    

Log in to reply
 

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