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:

   Use a stack to store the digits of the resulting number. 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.
   • Push the current digit onto the stack.
2. Remove Remaining Digits:

   If k is still greater than 0 after processing all digits, remove the top k digits from the stack.

3. Build the Result:

   Use a StringBuilder to collect the digits from the stack in reverse order. Remove leading zeros and return the result.

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 we need to remove all digits, return "0"
        if (k == num.length()) return "0";

        Stack stack = new Stack<>(); // To store the resulting digits
        int i = 0;

        // Process each digit in the number
        while (i < num.length()) {
            char c = num.charAt(i);

            // Remove digits from the stack while they are greater than the current digit
            // and we still need to remove more digits (k > 0)
            while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
                stack.pop();
                k--;
            }

            stack.push(c); // Push the current digit onto the stack
            i++;
        }

        // If there are still digits to remove, pop them from the stack
        while (k > 0) {
            stack.pop();
            k--;
        }

        // Build the resulting number from the stack
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        sb.reverse(); // Reverse the order to get the correct number

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

        return sb.substring(start);
    }
}