Java O(n*k) solution, 'n' is string length. how to make the code shorter?


  • 0

    this solution works, but I don't like it since the lines are too long. How to make shorter ?
    The thought:
    Removing 'k' elements from the numeric string, then the digit on the maximum position must be among the first 'k+1' digits in the numeric string, then find the first smallest in the first 'k+1' digits, clear those before (index is smaller than) it, then mark the right element of the smallest one as the new start, removing "k - cleared"

    public class Solution {
        public String removeKdigits(String num, int k) {
            if(num.length() <= k) {
                return "0";
            }
            char[] chars = num.toCharArray();
            char[] r = new char[chars.length - k];
            int start = 0;
            while(k > 0 && start < chars.length){
                if(start + k == chars.length){
                    // remove all 'k' elements until the last
                    Arrays.fill(chars, start, chars.length, (char)0);
                    break;
                }
                // find the smallest element in the window
                int windowSize = k + 1;
                int idxSmallest = -1;
                int smallest = Integer.MAX_VALUE;
                for(int i = start; i < start + windowSize && i < chars.length; i++){
                    if(chars[i] < smallest){
                        smallest = chars[i];
                        idxSmallest = i;
                    }
                }
                // clear all those before the smallest element
                Arrays.fill(chars, start, idxSmallest, (char)0);
                k -= idxSmallest - start;
                start = idxSmallest + 1;
            }
            
            StringBuffer sb = new StringBuffer();
            boolean firstNonZeroFound = false;  // introducing this var to avoid heading '0' in result
            for(int i = 0; i < chars.length; i++){
                if(chars[i] != 0) {
                    if(!firstNonZeroFound && chars[i] != '0'){
                        firstNonZeroFound = true;
                    }
                    
                    if(firstNonZeroFound){
                        sb.append(chars[i]);
                    }
                }
            }
            String result = sb.toString();
            return result.length() == 0 ? "0" : result;
        }
    }
    

Log in to reply
 

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