One pass O(n) Java solution, no stack needed


  • 0
    J
        public String removeKdigits(String num, int k) {
            StringBuilder sb = new StringBuilder(num);
            int count = 0, idx = 0;
            while (count < k && idx < sb.length() - 1) {
                if (sb.charAt(idx) > sb.charAt(idx + 1)) {
                    sb.deleteCharAt(idx);
                    count++;
                    idx = Math.max(idx - 1, 0);
                } else {
                    idx++;
                }
            }
            sb.delete(sb.length() - (k - count), sb.length());
            String res = sb.toString().replaceFirst("^0+", "");
            return res.isEmpty() ? "0" : res;
        }
    

    The basic idea is to replace the first index i where the ith number is greater than i+1th number. We do this repeatedly until we've hit the end of the string or we have done it k times.

    Then if we haven't replaced for k times, it means that the string is already in ascending order. What we need to do now is removing largest numbers from the string.

    Remember to remove leading 0s if any.


Log in to reply
 

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