Funcia
Lv.2greedymonotonic-stackstackstring

Smallest Number After Removing Digits

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A price tag shows the number num. Remove exactly k digits from it without changing the order of the remaining digits, and return the smallest possible number as a string.

  • Strip leading zeros from the result ("0200" becomes "200").
  • If nothing remains, or only zeros remain, return "0".

Examples

numkresult
"1432219"3"1219"
"10200"1"200"
"10"2"0"

Example 1 — Remove 4, 3 and the second 2 to get "1219".

Example 2 — Removing the leading 1 leaves "0200", which is "200".

Example 3 — Every digit is removed, so the answer is "0".

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(num: string, k: int) → string

Constraints

  • 1≤1 \le num.length ≤200,000\le 200{,}000
  • num consists of digits only and has no leading zero unless it is "0".
  • 0≤0 \le k ≤\le num.length

Expected complexity

Time
O(N)
Space
O(N)

Examples

numkExpected
"1432219"3"1219"
"10200"1"200"
"10"2"0"

Hint

Hint

A smaller leading digit always wins, so delete any digit that is larger than the digit right after it. Re-scanning from the start for the first such digit k times is O(Nk)O(Nk) and times out. Push digits onto a stack instead, popping larger digits while deletions remain; if deletions are left at the end, drop them from the top. Then strip leading zeros (empty → "0"). O(N)O(N).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4013verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.