Problem Description

You are given a string num that represents a non-negative integer and an integer k. Your task is to remove exactly k digits from num to create the smallest possible integer.

The problem asks you to strategically choose which k digits to remove so that the remaining digits form the minimum possible number. The digits that remain must keep their original relative order from the input string.

For example:

• If num = "1432219" and k = 3, you could remove the digits '4', '3', and '2' to get "1219", which is the smallest possible result
• If num = "10200" and k = 1, removing the '1' gives "0200" which becomes "200" after removing leading zeros
• If num = "10" and k = 2, removing both digits results in an empty string, which should return "0"

The key insight is that to minimize the resulting number, you want to maintain an increasing sequence of digits from left to right as much as possible. When you encounter a digit that is smaller than the previous one, it's beneficial to remove the larger previous digit(s) to make the overall number smaller.

The solution uses a stack-based greedy approach where:

1. For each digit in num, compare it with the top of the stack
2. If the current digit is smaller than the stack's top and you still have removals left (k > 0), pop the stack and decrement k
3. After processing all digits, take only the first remain digits (where remain = len(num) - k)
4. Remove any leading zeros and return "0" if the result is empty

Intuition

To find the smallest possible number after removing k digits, we need to understand what makes one number smaller than another. When comparing numbers with the same number of digits, the leftmost (most significant) digits matter the most. For instance, 1999 is smaller than 2000 because the first digit 1 is smaller than 2.

This leads us to a key observation: we want the smallest possible digits in the leftmost positions. When scanning through the string from left to right, if we encounter a digit that is smaller than the previous one, we should consider removing the previous (larger) digit to make room for the smaller one in a more significant position.

Consider num = "1432219" with k = 3. As we scan:

• We see 1, keep it
• We see 4, which is larger than 1, keep it for now
• We see 3, which is smaller than 4. Here's the crucial insight: removing 4 and keeping 3 gives us a smaller number because 13... is smaller than 14...
• We see 2, which is smaller than 3. Similarly, 12... is better than 13...

This suggests a greedy strategy: maintain a monotonically increasing sequence. Whenever we find a digit that breaks this pattern (i.e., it's smaller than the previous one), we remove the previous larger digits as long as we have removals remaining.

The stack data structure naturally fits this pattern. We can push digits onto the stack when they maintain the increasing order, and pop from the stack when we find a smaller digit that would create a better (smaller) result. This gives us the optimal local decision at each step, which leads to the globally optimal solution.

After processing all digits, if we still have removals left (when the input was already in increasing order), we simply take the first n - k digits. Finally, we handle edge cases like leading zeros and empty results.

Solution Approach

The implementation uses a greedy algorithm with a stack to maintain the smallest possible number at each step.

Here's how the algorithm works:

1. Initialize a stack to build our result and calculate remain = len(num) - k to know how many digits we need to keep.

2. Iterate through each character c in the input string num:

   • While we still have removals left (k > 0), the stack is not empty, and the top element of the stack is greater than the current character c:
     • Pop the stack (remove the larger digit)
     • Decrement k by 1
   • Append the current character c to the stack

3. Handle remaining removals: After processing all digits, if k > 0, it means the input was already in non-decreasing order. We only keep the first remain digits by slicing: stk[:remain]

4. Format the result:

   • Join the stack elements to form a string
   • Remove leading zeros using lstrip('0')
   • Return '0' if the result is empty (all digits were removed or only zeros remained)

Let's trace through an example with num = "1432219" and k = 3:

• Start with empty stack []
• Process '1': stack becomes ['1']
• Process '4': '4' > '1', so append: ['1', '4']
• Process '3': '3' < '4', pop '4', k = 2: ['1', '3']
• Process '2': '2' < '3', pop '3', k = 1: ['1', '2']
• Process '2': equal to top, append: ['1', '2', '2']
• Process '1': '1' < '2', pop '2', k = 0: ['1', '2', '1']
• Process '9': k = 0, just append: ['1', '2', '1', '9']
• Result: "1219"

The time complexity is O(n) where n is the length of the input string, as each digit is pushed and popped at most once. The space complexity is O(n) for the stack.

Example Walkthrough

Let's walk through a small example with num = "14325" and k = 2 to illustrate the solution approach.

Goal: Remove 2 digits to get the smallest possible number.

Step-by-step process:

1. Initialize:

   • Stack: []
   • remain = 5 - 2 = 3 (we need to keep 3 digits)
   • k = 2 (removals left)

2. Process '1':

   • Stack is empty, so push '1'
   • Stack: ['1'], k = 2

3. Process '4':

   • '4' > '1' (top of stack), so push '4'
   • Stack: ['1', '4'], k = 2

4. Process '3':

   • '3' < '4' (top of stack) and k > 0
   • Pop '4' from stack, decrement k
   • Stack: ['1'], k = 1
   • Now push '3'
   • Stack: ['1', '3'], k = 1

5. Process '2':

   • '2' < '3' (top of stack) and k > 0
   • Pop '3' from stack, decrement k
   • Stack: ['1'], k = 0
   • Now push '2'
   • Stack: ['1', '2'], k = 0

6. Process '5':

   • k = 0 (no removals left), so just push '5'
   • Stack: ['1', '2', '5'], k = 0

7. Final processing:

   • We've used all removals (k = 0)
   • Stack has exactly remain = 3 digits
   • Join stack: "125"
   • No leading zeros to remove
   • Result: "125"

Why this works: By removing the digits '4' and '3', we allowed smaller digits '2' and '5' to occupy more significant positions, creating the smallest possible 3-digit number from the original string while maintaining the relative order of the remaining digits.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input string num.

• The main loop iterates through each character in the string exactly once: O(n)
• The inner while loop might seem to add complexity, but each element can be pushed and popped from the stack at most once throughout the entire execution
• Therefore, the total number of operations across all iterations is at most 2n (each element pushed once and popped at most once)
• The lstrip('0') operation at the end takes O(n) in the worst case
• Overall time complexity remains O(n)

Space Complexity: O(n) where n is the length of the input string num.

• The stack stk can store at most n characters (when no digits are removed)
• The final string creation using ''.join(stk[:remain]) creates a new string of size at most n
• Therefore, the space complexity is O(n)

Common Pitfalls

1. Forgetting to Handle Remaining Removals

One of the most common mistakes is assuming that all k removals will be used during the main iteration. When the input digits are already in non-decreasing order (like "12345"), the while loop condition stack[-1] > digit will never be true, leaving k > 0 after processing all digits.

Incorrect approach:

def removeKdigits(self, num: str, k: int) -> str:
    stack = []
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # Bug: Not handling remaining k
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

Correct solution: Always slice the stack to keep only remaining_digits elements, which handles any unused removals:

remaining_digits = len(num) - k
# ... main loop ...
result = ''.join(stack[:remaining_digits]).lstrip('0')

2. Incorrectly Handling Leading Zeros

Another pitfall is removing leading zeros before taking the correct number of digits, or forgetting to handle the edge case where all remaining digits are zeros.

Incorrect approach:

# Bug: Removing zeros before slicing
result = ''.join(stack).lstrip('0')[:remaining_digits]

This would incorrectly count the removed zeros as part of the slice operation.

Correct solution: First slice to get the correct number of digits, then remove leading zeros:

result = ''.join(stack[:remaining_digits]).lstrip('0')
return result if result else '0'  # Return '0' if empty

3. Not Returning "0" for Empty Results

When all digits are removed or only zeros remain after removing leading zeros, the result string becomes empty. Failing to handle this case will return an empty string instead of "0".

Test case example:

• Input: num = "10", k = 2 → Both digits removed → Should return "0", not ""
• Input: num = "1000", k = 1 → Remove '1' → "000" → Should return "0", not ""