Editorial for String by Deletions
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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 .
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")
Comments