Solution Explanation: Greedy Algorithm

The problem asks to find the smallest possible integer after removing k digits from the input string num. A greedy approach is effective here. The core idea is to iteratively remove the largest digit that is to the left of a smaller digit. This is because removing a larger digit earlier will result in a smaller overall number.

Algorithm

1. Initialization: Use a stack (stk) to store digits. We also track the number of digits remaining (remain) after removing k digits. remain = len(num) - k.

2. Iteration: Iterate through each digit (c) in the input string num.

3. Greedy Removal: While k is greater than 0 and the stack is not empty and the top of the stack (stk[-1]) is greater than the current digit (c):

   • Pop the top of the stack (remove the larger digit).
   • Decrement k (we've removed one digit).

4. Push to Stack: Push the current digit (c) onto the stack.

5. Handle Remaining k: After the loop, if k is still greater than 0 (meaning we need to remove more digits), pop the last k digits from the stack. This handles cases where the digits are monotonically increasing (e.g., "12345").

6. Remove Leading Zeros: Convert the stack to a string, remove any leading zeros, and handle the case where the result is an empty string (representing 0).

Time and Space Complexity

• Time Complexity: O(N), where N is the length of the input string num. The algorithm iterates through the string once. Stack operations (push and pop) take constant time.
• Space Complexity: O(N) in the worst case, as the stack could potentially store all digits of the input string.

Code Examples (with explanations)

Python:

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stk = []
        remain = len(num) - k
        for c in num:
            while k and stk and stk[-1] > c: # Greedy step: remove larger digit to the left of smaller
                stk.pop()
                k -= 1
            stk.append(c) # Add current digit
        return ''.join(stk[:remain]).lstrip('0') or '0' # Remove leading zeros, handle empty string

Java:

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stk = new StringBuilder(); // Use StringBuilder for efficient string manipulation
        for (char c : num.toCharArray()) {
            while (k > 0 && stk.length() > 0 && stk.charAt(stk.length() - 1) > c) {
                stk.deleteCharAt(stk.length() - 1); // remove larger digit
                --k;
            }
            stk.append(c);
        }
        //Handle remaining k
        while (k-- > 0) stk.deleteCharAt(stk.length()-1);
        
        int i = 0;
        while (i < stk.length() && stk.charAt(i) == '0') i++; // remove leading zeros
        return i == stk.length() ? "0" : stk.substring(i);
    }
}

The other languages (C++, Go, TypeScript) follow a similar pattern, adapting the core algorithm to the specifics of each language's syntax and data structures. The key ideas of the greedy algorithm remain consistent across all implementations.