Remove K Digits

Oracle

2020-05-13

402. Remove K Digits

Question:

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.

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.

Solution:

This problem using the idea of Greedy which keeps the string in an increasing order. Cannot use parseInt to remove the leading zero because the number is out of bound.
String VS String Builder:
Design for safety reason, String is immutable and will use multiple copies of memory. Thus, to save memory and time, we need to use StringBuilder which only use one copy of memory.

class Solution {
    public String removeKdigits(String num, int k) {
        // Edge Case Handling
        if (k == 0) {
            return num;
        }
        if (k == num.length()) {
            return "0";
        }
        
        Stack<Character> stack = new Stack<Character>();
        
        // Keep the string an increasing order
        for (char c : num.toCharArray()) {
            while (k > 0 && !stack.empty() && stack.peek() > c) {
                k--;
                stack.pop();
            }
            stack.push(c);
        }
        
        // Removing the ending if we have extra k
        for (int i = 0; i < k; i++) {
            stack.pop();
        }
        
        // Building into a string using StringBuilder
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        sb.reverse();

        // Remove any leading zero, cannot use parseInt()
        while(sb.length() > 1 && sb.charAt(0) == '0'){
            sb.deleteCharAt(0);
        }
        return sb.toString();
    }
}