LeetCode 402. Remove K Digits

Question

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

• 1 <= k <= num.length <= 105
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

Source: https://leetcode.com/problems/remove-k-digits/

Solution

We use the greedy thought. Assume you are given a set of numbers, how to order these numbers to make the value as small as possible? Obviously, we should place small numbers on high digits.

In stack, we try to make elements ascending. Before running out of remove operations stack is monotonically ascending, because we keep kicking out large numbers and let small numbers be put on high digits.

Note that for Deque, pop() = pollFirst() = removeFirst(), push() = offerFirst() = addFirst(). Because for a linked-list based deque, its head is the top of stack.

public String removeKdigits(String num, int k) {
    if (num == null || num.length() <= k) {
        return "0";
    }
    StringBuilder builder = new StringBuilder();
    Deque<Character> stack = new LinkedList<>();
    // from left to right, try our best to make elements ascending
    for (int i = 0; i < num.length(); i++) {
        char digit = num.charAt(i);
        while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    // apply unused remove operations
    // just remove the tail because the stack is ascending
    while (k > 0) {
        stack.pop();
        k--;
    }
    // remove leading zeros
    while (!stack.isEmpty() && stack.getLast().equals('0')) {
        stack.pollLast();
    }
    while (!stack.isEmpty()) {
        builder.append(stack.pop());
    }
    if (builder.length() == 0) {
        return "0";
    } else {
        return builder.reverse().toString();
    }
}