remove k digits

XXX. Remove K Digits

Greedy Algorithm

Stack

Problem Statement:

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

Return the smallest number in string format after removing k digits. If the resulting number has leading zeros, trim them. If the resulting number is empty, return "0".

Algorithm:

1. Use a Stack:

   The intuition is to use a stack to greedily maintain the smallest possible number by selectively retaining digits. Iterate through each digit of num, and for each digit:

   • Remove the top of the stack if it is greater than the current digit and k > 0. This ensures the number is as small as possible by eliminating digits that are "less optimal" for forming the smallest number.
   • Push the current digit onto the stack as a potential candidate for the resulting number.

   This approach effectively removes the largest digits first while preserving the order of digits in the original number.

2. Remove Remaining Digits:

   If k is still greater than 0 after processing all digits, remove the top k digits from the stack. These digits are the largest remaining ones, as smaller ones have already been retained.

3. Build the Result:

   Collect the digits from the stack into a StringBuilder in reverse order to construct the resulting number. Then, remove leading zeros to ensure the final number is properly formatted.

Complexity:

Time Complexity: O(n), where n is the length of num. Each digit is pushed and popped from the stack at most once.
Space Complexity: O(n), for the stack to store digits.

Java Implementation:

class Solution {
    public String removeKdigits(String num, int k) {
        if (k == num.length()) return "0";

        Stack stack = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);

            // Greedily remove digits from the stack if they are larger than the current digit
            while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        // Remove remaining digits if k > 0
        while (k-- > 0) stack.pop();

        // Build the final number
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pop());

        sb.reverse(); // Reverse the collected digits

        // Remove leading zeros
        int start = 0;
        while (start < sb.length() - 1 && sb.charAt(start) == '0') start++;

        return sb.substring(start);
    }
}