Remove K Digits to Form the Smallest Number

Remove exactly k digits from a string of digits to produce the smallest possible integer.

greedy stack string optimization

You are given a non-negative integer represented as a string `num` and an integer `k` where `0 <= k <= len(num)`. Your task is to remove exactly `k` digits from `num` so that the remaining string (in the same order) represents the smallest possible integer. The result must not contain leading zeros unless the result is exactly `'0'`. Return the resulting number as a string.

Implement the function:
```python
def remove_k_digits(num: str, k: int) -> str:
    ...
```

Constraints:
- `1 <= len(num) <= 100000`
- `0 <= k <= len(num)`
- `num` consists only of digits ('0'-'9') and has no leading zeros except the single digit '0'.
- Your algorithm must run in `O(n)` time and `O(n)` space.

Note: The input string may be large, so an efficient greedy approach is required. The standard solution uses a monotonic stack concept with deletions when a digit is greater than the next digit.

Constraints

1 <= len(num) <= 100000; 0 <= k <= len(num); num consists only of digits '0'-'9' with no leading zeros (except '0' itself). Time O(n), space O(n).

Example

>>> remove_k_digits('1432219', 3)
'1219'
>>> remove_k_digits('10200', 1)
'200'
>>> remove_k_digits('10', 2)
'0'
>>> remove_k_digits('9', 1)
'0'

45 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think greedy: scan digits left to right, removing a previous digit if it's larger than the current one, because that makes the number smaller at an earlier position.

Use a stack to keep the digits you want to keep; when you see a digit smaller than the stack top and you still have removals left, pop the stack.

After the scan, if you still have removals left, remove digits from the end of the stack.

Finally, remove leading zeros (but if the result becomes empty, return '0').

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.