Number Reduction
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1500
Tags: 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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3

Example output:
1
1337
321
344128
7052

Editorial:
To begin with, in order to minimize the answer, we minimize the first (highest) digit of the answer. Let's check if the highest digit can be equal to $$$1$$$. To do this, there must be $$$1$$$ in the number among the first $$$k+1$$$ digits (because we can delete no more than $$$k$$$ of them). If $$$1$$$ is not among the first $$$k+1$$$ digits, then we proceed to check $$$2$$$, then $$$3$$$ and so on. Otherwise, let's say that this digit is the first digit of the answer, and remove all the digits before it and itself from the number $$$x$$$, reducing the value of $$$k$$$. For example, if $$$x=741819$$$ and $$$k=4$$$, then after the operation $$$ans=1$$$, $$$x=819$$$ and $$$k=2$$$. Thus, we get the same problem, but with new values of $$$x$$$ and $$$k$$$, which is solved by the same algorithm (searching for the minimum first digit). The only difference is that after the first such iteration, the first digit can be equal to $$$0$$$.
It remains to understand how to quickly check whether the digit $$$d$$$ is among the first $$$k+1$$$ positions of the number. To do this, let's write, for each digit, its positions in the original number $$$x$$$. At each iteration of the algorithm, the current value of $$$x$$$ is some suffix of the original $$$x$$$, let it be the suffix of positions $$$[lst; n]$$$, where $$$n$$$ is the length of the original $$$x$$$. Now to check the digit, it is enough to look into its array of positions and find the minimum occurrence greater than or equal to $$$lst$$$. To do this, you can use binary search or delete all positions that are strictly less than $$$lst$$$ from the array or set (because the value of $$$lst$$$ only increases for subsequent iterations of the algorithm).
Thus, the solution works in $$$O(n)$$$ or $$$O(n\log{n})$$$ time.