Number Reduction (Codeforces 1765N)
Tags: Greedy, greedy

You are given a positive integer $$$x$$$.You can apply the following operation to the number: remove one occurrence of any digit in such a way that the resulting number does not contain any leading zeroes and is still a positive integer. For example, $$$10142$$$ can be converted to $$$1142$$$, $$$1042$$$, $$$1012$$$ or $$$1014$$$ (note that $$$0142$$$ is not a valid outcome); $$$10$$$ can be converted to $$$1$$$ (but not to $$$0$$$ since it is not positive).Your task is to find the minimum positive integer that you can obtain from $$$x$$$ if you can apply the aforementioned operation exactly $$$k$$$ times.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.The first line of each test case contains a single integer $$$x$$$ ($$$1 \le x < 10^{500000}$$$).The second line contains a single integer $$$k$$$ ($$$0 \le k < |x|$$$), where $$$|x|$$$ is the length of the number $$$x$$$.The sum of $$$|x|$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output: For each test case, print one integer — the minimum positive number that you can obtain from $$$x$$$ if you can apply the operation exactly $$$k$$$ times.


Sample Inputs:
5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3

Sample Outputs:
1
1337
321
344128
7052

Solution (Python):
import sys
input = sys.stdin.readline

def s():
    s = input()
    k = int(input())
    (m, ind) = (s[0], 0)
    for i in range(k + 1):
        if '0' < s[i] < m:
            m = s[i]
            ind = i
    k -= ind
    (res, l) = (m, [])
    for (j, e) in enumerate(s[ind + 1:]):
        if k == 0:
            l += [*s[ind + 1 + j:]]
            break
        if l == [] or e >= l[-1]:
            l += [e]
        elif k:
            while l != [] and l[-1] > e and k:
                k -= 1
                l.pop()
            l += [e]
    if k:
        l = l[:len(l) - k]
    for i in l:
        res += i
    return res
t = int(input())
r = ''
for _ in range(t):
    r += s()
print(r)

Solution (Python):
import sys

def I():
    return sys.stdin.readline()

def II():
    return int(I())

def MII():
    return map(int, I().split())

def slove(s: str, k: int) -> str:
    j = 0
    for (i, ch) in enumerate(s[:k + 1]):
        if ch != '0' and ch < s[j]:
            j = i
    k -= j
    st = [s[j]]
    for (i, ch) in enumerate(s[j + 1:-1]):
        while len(st) > 1 and k and (ch < st[-1]):
            st.pop()
            k -= 1
        st.append(ch)
    return ''.join(st[:len(st) - k])
T = II()
for _ in range(T):
    s = I()
    k = II()
    print(slove(s, k))

Solution (Python):
from dataclasses import dataclass
from time import time
import math

@dataclass
class MyInput:
    t: int
    test_cases: list

def get_input():
    t = int(input())
    test_cases = []
    for _ in range(t):
        x = input()
        k = input()
        test_cases.append((x, k))
    return MyInput(t=t, test_cases=test_cases)

def get_sample_idx_first(x, k):
    (_, min_idx) = min(((val, idx) for (idx, val) in enumerate(x[:k + 1]) if val != '0'))
    return min_idx

def resolve(x, k):
    if k == 0:
        return x
    ret = []
    min_value_idx = get_sample_idx_first(x, k)
    ret.append(x[min_value_idx])
    k = k - min_value_idx
    for i in range(min_value_idx + 1, len(x)):
        while len(ret) > 1 and k and (ret[-1] > x[i]):
            ret.pop()
            k -= 1
        ret.append(x[i])
    while len(ret) > 1 and k:
        ret.pop()
        k -= 1
    return ''.join(ret)

def main():
    myinput = get_input()
    for i in range(myinput.t):
        (x, k) = myinput.test_cases[i]
        k = int(k)
        print(resolve(x, k))
    return myinput
if __name__ == '__main__':
    main()