Remove K Digits
Medium · Stack & Strings · String · Stack · Greedy · Monotonic Stack
Problem
You are given a string num holding a non-negative integer and an integer k. Delete exactly k digits from num, keeping the remaining digits in their order, so that the number left is as small as possible. Return it as a string.
The result must not have leading zeros. If no digits remain, or only zeros remain, return "0".
Examples
Input: num = "52413", k = 2 Output: "213"
Deleting 5 and 4 leaves 213, the smallest three-digit result.
Input: num = "30200", k = 1 Output: "200"
Deleting 3 leaves 0200, written without its leading zero.
Input: num = "7", k = 1 Output: "0"
Deleting the only digit leaves nothing, which counts as 0.
Constraints
- 1 <= k <= len(num) <= 10^5
- num contains only digits
- num has no leading zeros, except for the number 0 itself
Approaches
- Baseline: delete the first peak, k times — time O(n · k), space O(n)
Follow-up
The same stack builds the smallest subsequence of a fixed length from any sequence. How would you adapt it to keep the largest number instead, or to pick exactly one copy of each distinct letter (two of the use cases)?
Related problems
Start free on Cariara · Coding problems · System design studio
