Show problems as
Classic problem #402MediumStringStackGreedyMonotonic Stack

Remove K Digits

Real-world version: Trim the Freight Code
Tracked in this browser only
Read Remove K Digits on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A freight terminal stamps every pallet with a routing code, handed to you as the digit string num. Before the pallet is re-stamped, the terminal is allowed to erase exactly k of the digit positions. Whatever survives keeps the left-to-right arrangement it already had; surviving digits are never rearranged.

Pick the positions to erase so the re-stamped code reads as the lowest whole number that any legal erasure can produce, and hand that code back as a string. Zeros sitting in front of the first non-zero survivor are dropped when the code is stamped. Should the erasure consume every position, the terminal stamps "0".

Examples

Example 1

Input
num = "4297", k = 2
Output
"27"

Erasing the 4 and the 9 leaves 2 followed by 7. No other pair of survivors reads lower than 27.

Example 2

Input
num = "1122", k = 1
Output
"112"

The digits never step down, so the cheapest erasure is the rightmost position.

Example 3

Input
num = "70081", k = 3
Output
"0"

Holding on to the two zeros stamps a value of zero once the front zero is dropped.

Constraints

  • 1 <= k <= num.length <= 10^5
  • num is made up of digit characters only.
  • num carries no zero in front unless it is the lone digit 0.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_kdigits(num: str, k: int) -> str:
Java
public String removeKdigits(String num, int k)

More on the same topics