Java solution


  • 0
    L

    Remove one digit at a time and do this k times. Time complexity is O(N* k). Is there a better solution that we can remove more than one digit at a time?

    	public String removeKdigits(String num, int k) {
    		String ans = num;
    		for (int i = 1; i <= k; i++)
    			ans = removeOneDigit(ans);
    		return ans;
    	}
    
    	private String removeOneDigit(String num) {
    		int n = num.length();
    		int index = n - 1;
    		for (int i = 0; i < n - 1; i++) {
    			if (num.charAt(i) > num.charAt(i + 1)) {
    				index = i;
    				break;
    			}
    		}
    
    		StringBuilder sb = new StringBuilder();
    		for (int i = 0; i < n; i++) {
    			char digit = num.charAt(i);
    			if (sb.length() == 0 && digit == '0' || i == index)
    				continue;
    			sb.append(digit);
    		}
    		return sb.length() == 0 ? "0" : sb.toString();
    	}
    

  • 0
    B

    Thanks for the good idea. Here is my code :D

    public String removeKdigits(String num, int k) {
            StringBuilder sb = new StringBuilder(num);
            for(; k > 0; k--){
              /*at most k loops(if length == 0, we early break), each loop deletes one digit.*/
                if(sb.length() == 0) break;
                int index = sb.length()-1;
                for(int i = 0; i < sb.length()-1; i++){
                  /*core part of algotithm, if ascending, then we delete*/
                    if(sb.charAt(i) > sb.charAt(i+1)){
                        index = i;
                        break;
                    }
                }
                sb.deleteCharAt(index);
                int start = 0;
                while(start < sb.length() && sb.charAt(start)=='0') start++;
                sb.delete(0, start);
            }
            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.