Smallest Number After Deletions
MediumStack
Problem
A ticket number is given as a string of digits num. You must delete exactly k digits; the remaining digits keep their order.
Return the smallest possible resulting number as a string, without leading zeros. If nothing (or only zeros) remains, return "0".
Example 1
- Input:
- num = "4321", k = 2
- Output:
- "21"
Delete the two largest leading digits 4 and 3.
Example 2
- Input:
- num = "30400", k = 1
- Output:
- "400"
Deleting 3 leaves "0400", which is 400.
Example 3
- Input:
- num = "12", k = 2
- Output:
- "0"
Constraints
- 1 ≤ k ≤ num.length ≤ 10^5
- num contains only digits
- num has no leading zeros unless it is "0"
Hint
Show the first hint
Numbers with the same length compare by their first differing digit. Which digit position matters most?
Walkthrough
How to approach it
01Clarify before coding
- Must I delete exactly k digits? Yes.
- How are leading zeros handled? Strip them; an empty result is "0".
- Can num be very long? Up to 10^5 digits, so no conversion to a number type.
02Brute force
Try every way to choose which k digits to delete and keep the smallest result.
Cost: C(n, k) combinations, each costing O(n) to build and compare: exponential.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.