434. Remove K Digits
A lottery ticket shows a long string of decimal digits written in num. The organiser is allowed to scratch out exactly k of the digits, in any positions, and the remaining digits close up in their original order to form a new number. The organiser wants that new number to be as small as possible.
Return the smallest possible resulting number as a string. Leading zeros that appear after the scratching must be dropped, so "0012" is reported as "12". If every digit is removed, or only zeros remain, the answer is "0". The input has no restriction on leading zeros, k is never larger than the length of num, and the string can be up to 8,000 digits long.
Example 1
- Input:
- num = "5273941", k = 3
- Output:
- "2341"
- Explanation:
Removing 5, 7 and 9 leaves 2, 3, 4, 1 giving 2341, the smallest possible after three removals.
Example 2
- Input:
- num = "30200", k = 1
- Output:
- "200"
- Explanation:
Removing the 3 gives 0200 which becomes 200 after dropping the leading zero; removing anything else leaves a number starting with 3.
Constraints
1 ≤ num.length ≤ 8000
0 ≤ k ≤ num.length
num consists of digits only and may start with zeros.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)