Leetcode 402. Remove K Digits

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

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

This problem was quite difficult for me and I had to look up the solution and reasoning to complete it. Basically, the total count of strings with K characters removed is N Choose (N-K) where N is the length of the string and K is the number of characters to delete. The running time to examine all of these strings is exponential and therefore inefficient.

The approach to solving the problem is first interpretating the string as a number. Then it is realizing that the digits should be examined from left to right as the left digits hold the most value. Further examination shows that the starting from the left, any digit to the left of a digit that is also greater should be discarded. A stack is used to hold the digits that will be used to create the final string. The explanation below elaborates further.

My solution:

class Solution {
    public String removeKdigits(String num, int k) {

        if (num.isEmpty()) {
            return "0";
        }
        Deque<Character> deque = new ArrayDeque<>();
        deque.addFirst(num.charAt(0));
        int cnt = 0;
        for (int i = 1; i < num.length(); i++) {
            int curDig = num.charAt(i) - '0';
            while (deque.isEmpty() == false && (deque.peekFirst() - '0') > curDig && cnt < k) {
                deque.removeFirst();
                cnt++;
            }

            if (deque.size() > 0 || num.charAt(i) != '0') {
                deque.addFirst(num.charAt(i));
            }
        }

 
        
        while (!deque.isEmpty() && cnt < k) {     
            deque.removeFirst();
            cnt++;
        }
     
        
        StringBuilder sb = new StringBuilder();
        while(!deque.isEmpty()) {
            sb.insert(0,deque.removeFirst());
        }
        
        String s = sb.toString();
        if (s.length() == 0) {
            return "0";
        }
         
        return s;
        
    }
}

Explanation:

Line 4 checks if the string is empty and returns a “0” for this trivial case.

Line 7 intializes the stack that is used to hold candidates for the final string.

Line 8 adds the leading digit to the stack and the digit is a candidate for the final string.

Line 10 is the main loop that iterates through the rest of the digits. The first iteration of the loops compares the current digit with the digit on the stack, and every iteration afterwards compares the current digit with the digits on the stack.

Line 11 - 15 compares the current digit (int curDig = num.charAt(i) - ‘0’) with the digits on the stack. Line 12 does the actual comparison in a while loop. While there are digits on the stack that are greater than the current digit, remove those digits from the stack until the stack runs out or the number of digits removed (cnt) is equal to k.

Line 17 adds the current digit to the stack. for consideration for the final string. The condition checks (deque.size() > 0

num.charAt(i) != ‘0’) ensure that the digit added to the stack will not result in a leading 0.

Line 24 removes digits from the stack if number of digits removed is less than k and there are digits available on the stack. This loop will execute if the number in the stack has monotonically increasing digits. For example if the number is 12345, then the least significant digits(the top of the stack) would be removed.

Line 30-38 wrap the digits in a stringbuilder object in the correct order such that the top of the stack is the least significant digit. Line 36 is a special where there are no digits in the stack and therefore a “0” should just be returned.

Line 40 returns the answer