Remove K Digits Stack

Use a monotonic stack to remove k digits and produce the smallest possible number.

stack string greedy monotonic

Given a string `num` representing a non-negative integer (no leading zeros except for the single digit '0'), and an integer `k`, return the smallest possible integer as a string by removing exactly `k` digits from `num` while keeping the order of the remaining digits the same.

Implement the function `def remove_k_digits(num: str, k: int) -> str:`. If all digits are removed, return `"0"`. The final answer must not have leading zeros unless the answer is exactly `"0"`.

**Examples:**
- `remove_k_digits("1432219", 3)` → `"1219"`
- `remove_k_digits("10200", 1)` → `"200"`

Constraints

- `1 <= len(num) <= 1000`
- `0 <= k <= len(num)`
- `num` consists of digits only (no leading zeros except possibly the single-digit '0').
- Time complexity should be O(n), where n is the length of `num`.

Example

>>> remove_k_digits("1432219", 3)
'1219'
>>> remove_k_digits("10200", 1)
'200'
>>> remove_k_digits("10", 2)
'0'
>>> remove_k_digits("112", 1)
'11'

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Simulate the process by maintaining a stack of digits that are currently kept. Removing a digit is like popping it from the stack when a smaller digit appears after a larger one.

You don't need to generate all combinations. Use a greedy approach: whenever the next digit is smaller than the last kept digit, pop it (if you still have removals left).

After processing all digits, if k is still positive, remove the last k digits from the stack.

Finally, strip leading zeros. If the stack is empty, return '0'.

Test Results

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