Java greedy solution with O(N × k)


  • 0
    T

    Ascending order is the choice that can minimize the number among all of combinations.
    So, greedy selection can be applied when iterating from start.

    "The character to remove is what breaks ascending order,"

    So if meets the character that breaks ascending order while iterating, remove it immediately.

    If k still remains after finishing iterating, remove k characters from end.

    Running time is O(N × k) = (delete 1 character from StringBuilder O(N)) × k times
    (If character can be deleted in constant time, Running time would be O(N).)

        public String removeKdigits(String num, int k) {
            if (num.length() <= k) {
                return "0";
            }
            StringBuilder builder = new StringBuilder(num);
            int index = 0;
            int prev = -1;
            while (k > 0) {
                if (index < builder.length()) {
                    int current = builder.charAt(index) - '0';
                    if (prev > current) {
                        // If meet the character that is breaking ascending order, delete it.
                        builder.deleteCharAt(index - 1);
                        // index should decrease by 1, because previous character is deleted.
                        index--;
                        // reset prev character.
                        int prevIndex = index - 1;
                        if (prevIndex < 0) {
                            prev = -1;
                        } else {
                            prev = builder.charAt(prevIndex) - '0';
                        }
                        k--;
                    } else {
                        // If ascending, keep going.
                        index++;
                        prev = current;
                    }
                } else {
                    // If the character to remove still remains after iterating,
                    // delete them from end.
                    builder.delete(builder.length() - k, builder.length());
                    k = 0;
                }
            }
    
            // trim '0' if exist
            int zeroCount = 0;
            while (zeroCount < builder.length() && builder.charAt(zeroCount) == '0') {
                zeroCount++;
            }
            if (zeroCount == builder.length()) {
                zeroCount = builder.length() - 1;
            }
            if (zeroCount > 0) {
                builder.delete(0, zeroCount);
            }
            return builder.toString();
        }
    

Log in to reply
 

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