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.

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.

Constraints:

• 1 <= k <= num.length <= 10^5
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

## Problem Description

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

For example:

*   If `num = "1432219"` and `k = 3`, the output should be `"1219"`. Removing `4`, `3`, and `2` yields the smallest result.
*   If `num = "10200"` and `k = 1`, the output should be `"200"`. Removing the leading `1` is optimal.
*   If `num = "10"` and `k = 2`, the output should be `"0"`. Removing both digits leaves nothing, which is represented as `0`.

## Naive Solution

A naive solution would be to generate all possible subsequences of length `n - k` (where `n` is the length of the original number) and then find the smallest one among them. This approach involves generating combinations, which can be computationally expensive.

For example, with "1231234" and k = 3, you could remove (1,2,3), (1,2,1), (1,2,2) and etc.  This is very slow!

## Optimal Solution: Greedy with Stack

The optimal solution uses a greedy approach with a stack (or a similar data structure) to maintain a monotonically increasing sequence. The basic idea is to iterate through the digits of the number and maintain a stack where digits are added such that the digits at the bottom are smaller than digits on top, thus forming a monotonically increasing stack. If we encounter a digit that's smaller than the top of the stack, it means we can potentially remove the top of the stack (i.e., a larger digit) to obtain a smaller number.

Here's the algorithm:

1.  Initialize an empty stack.
2.  Iterate through the digits of the input number:
    *   While the stack is not empty, `k > 0`, and the current digit is smaller than the top of the stack, pop the top element from the stack and decrement `k`.
    *   Push the current digit onto the stack.
3.  If `k` is still greater than 0, remove the remaining `k` digits from the end of the stack (the largest elements).
4.  Construct the result string from the stack.
5.  Remove any leading zeros from the result.
6.  If the resulting string is empty, return "0".

```python
def remove_k_digits(num: str, k: int) -> str:
    stack = []
    for digit in num:
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # Remove remaining digits from the end if k > 0
    while k > 0:
        stack.pop()
        k -= 1

    # Construct the result string
    result = "".join(stack)

    # Remove leading zeros
    result = result.lstrip("0")

    # If the result is empty, return "0"
    return result if result else "0"

# Example Usage
print(remove_k_digits("1432219", 3))  # Output: 1219
print(remove_k_digits("10200", 1))  # Output: 200
print(remove_k_digits("10", 2))  # Output: 0
print(remove_k_digits("1111111", 3)) # Output: 1111
print(remove_k_digits("1234567890", 9)) # Output: 0

Big(O) Time Complexity Analysis

The time complexity of this algorithm is O(n), where n is the length of the input number. This is because each digit is visited at most twice (once when it's pushed onto the stack and once when it's potentially popped from the stack).

• The main loop iterates through each digit of the input number num. This loop runs n times, where n is the length of num.
• Inside the loop, the while condition might cause some digits to be popped from the stack. In the worst case, each digit is pushed and popped once.
• The remaining operations (joining the stack, removing leading zeros) take O(n) time in the worst case as well. lstrip() is also O(n).
• Therefore, the overall time complexity is O(n). There's no nested looping or anything that'll cause a higher run-time.

Big(O) Space Complexity Analysis

The space complexity of this algorithm is O(n), where n is the length of the input number. This is because the stack can contain at most n digits.

• The stack stack stores digits. In the worst-case scenario, all n digits of num might be pushed onto the stack (e.g., if num is in increasing order and k is 0). For example, if num = "12345" and k = 0, then the stack will hold all the digits.
• The space required for the stack is thus O(n).
• The other variables used (like digit, k, and result) take constant space.
• Hence, the overall space complexity is O(n).

Edge Cases

1. Leading Zeros: The result must not contain leading zeros. The code removes leading zeros using lstrip("0").
2. Empty Result: If all digits are removed (i.e., k is equal to the length of num), the result should be "0". The code handles this by returning "0" if the result string is empty after removing leading zeros.
3. Input in Increasing Order: If the input is in increasing order, the algorithm should remove the last k digits. For example, remove_k_digits("12345", 3) should return "12".
4. k = 0: If k is zero, no digits need to be removed, and the original number should be returned (after removing leading zeros). Although not explicitly implemented in the cleanup stage, the algorithm effectively handles this case.
5. Large Inputs: The algorithm should work efficiently for large input strings (up to 10^5 digits). The O(n) time complexity ensures reasonable performance even for large inputs.