Editorial for String by Deletions

Approach

We want the leftmost remaining digits to be as small as possible.

Scan the string from left to right and maintain a stack of chosen digits. When the current digit is smaller than the top of the stack, deleting that larger top digit is always better than keeping it before the smaller digit. So while we still have deletions left, keep popping larger previous digits.

After processing the whole string, if we still have deletions left, remove digits from the end. Those are the least significant remaining digits.

Finally, strip leading zeroes from the built string. If nothing remains, print 0.

Time complexity is $O(|s|)$.

Solution (Python)

s = input().strip()
k = int(input())

stack: list[str] = []

for digit in s:
    while k > 0 and stack and stack[-1] > digit:
        stack.pop()
        k -= 1
    stack.append(digit)

if k > 0:
    stack = stack[:-k]

answer = "".join(stack).lstrip("0")
print(answer or "0")