Nearest Beautiful Number (hard version)
Contest: Codeforces Round 739 (Div. 3)
Difficulty rating: 2100
Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dp, greedy

It is a complicated version of problem F1. The difference between them is the constraints (F1: $$$k \le 2$$$, F2: $$$k \le 10$$$).

You are given an integer $$$n$$$. Find the minimum integer $$$x$$$ such that $$$x \ge n$$$ and the number $$$x$$$ is $$$k$$$-beautiful.

A number is called $$$k$$$-beautiful if its decimal representation having no leading zeroes contains no more than $$$k$$$ different digits. E.g. if $$$k = 2$$$, the numbers $$$3434443$$$, $$$55550$$$, $$$777$$$ and $$$21$$$ are $$$k$$$-beautiful whereas the numbers $$$120$$$, $$$445435$$$ and $$$998244353$$$ are not.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le 10$$$).

Output format:
For each test case output on a separate line $$$x$$$ — the minimum $$$k$$$-beautiful integer such that $$$x \ge n$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10

Example output:
2021
181111
34533
724542
999999999
12345678

Editorial:
Suppose the number $$$n$$$ contains $$$m$$$ digits and its decimal representation is $$$d_1d_2 \dots d_m$$$. The desired number $$$x$$$ isn't greater than the number consisting of $$$m$$$ digits $$$9$$$. This number is $$$1$$$-beautiful whereas any $$$1$$$-beautiful number is at the same time $$$k$$$-beautiful, so $$$x$$$ contains at most $$$m$$$ digits. At the same time, $$$x \ge n$$$ so $$$x$$$ contains at least $$$m$$$ digits. Therefore, the desired number contains exactly $$$m$$$ digits.
Since we search for the minimum $$$x$$$, we need to minimize first of all the first digit, only then the second digit, etc. Therefore, we need to find a prefix of the decimal representation of $$$n$$$ such that is a prefix of the decimal representation of $$$x$$$. Let's do it greedily.
Short solution, works in $$$O(m^2)$$$
Let's find the maximum prefix of $$$n$$$ such that contains no more than $$$k$$$ distinct numbers. Suppose the prefix has the length $$$p$$$. If $$$p = m$$$, then $$$n$$$ is already $$$k$$$-beautiful, let's output it. Otherwise, let's increase the prefix like a number by $$$1$$$, e.g. if $$$n = 1294$$$ and $$$p = 3$$$, then we increase $$$129$$$ by $$$1$$$, the resulting prefix is $$$130$$$. All other digits ($$$d_{p + 2}, d_{p + 3}, \dots, d_m$$$), let's set to zeroes (e.g. if $$$n = 1294$$$ and $$$p = 3$$$, then $$$n$$$ will be turned into $$$1300$$$). The answer for the old $$$n$$$ is the answer for the new $$$n$$$. To get the answer for the new $$$n$$$, let's start the described procedure once again preparing the new $$$n$$$.
Long solution, works in $$$O(mk)$$$
Let's find the maximum prefix of $$$n$$$ such that contains no more than $$$k$$$ distinct numbers. It's possible to do using a $$$map$$$ in which for each digit (the key) the number of its occurrences in the prefix is stored. For an empty prefix, the $$$map$$$ is empty. If we increase the prefix length by $$$1$$$, we need to check that $$$map$$$ contains no more than $$$k$$$ keys and add a new key with the value $$$1$$$ or increase the value of an existing key. If the length of the found prefix is equal to the length of the whole decimal representation, the given number is already $$$k$$$-beautiful so the answer is $$$n$$$.
Otherwise, the found prefix may not be a prefix of the desired number. Let's change the digits of the decimal representation of $$$n$$$ to turn it into the desired number $$$x$$$. Let's start the following procedure: suppose we consider a prefix with the length equal to $$$p$$$. First, let's find out, is it possible to increase the first element out of the prefix (i. e. $$$d_{p + 1}$$$). We need to do it because if we consider the length $$$p$$$, then the prefix with the length $$$p + 1$$$ cannot be unchanged so the element $$$d_{p + 1}$$$ must be changed whereas it cannot be decreased because, in this case, we will get the number which is less than $$$n$$$. If we can increase the element $$$d_{p + 1}$$$ so that the prefix with the length $$$p + 1$$$ has at most $$$k$$$ distinct digits, the only thing that is remained to do is to fill the remaining digits $$$d_{p + 2}, d_{p + 3}, \dots d_m$$$ somehow greedily and output the result. If we cannot increase the element $$$d_{p + 1}$$$, let's decrease the length of the considered prefix $$$p$$$ by $$$1$$$ updating the $$$map$$$ (let's decrease the value corresponding to the key $$$d_{p}$$$ by $$$1$$$, then, if it's equal to $$$0$$$, we remove the key $$$d_{p}$$$ from the $$$map$$$).
Consider, how and under what conditions we can change $$$d_{p + 1}$$$ and the following digits:
1. If $$$d_{p + 1} = 9$$$, it's impossible.
2. Suppose the considered prefix contains less than $$$k$$$ distinct digits (the number of the keys in the $$$map$$$ is less than $$$k$$$). In this case, we can replace the digit $$$d_{p + 1}$$$ with the value $$$d_{p + 1} + 1$$$ so the prefix with the length $$$p + 1$$$ will not contain more than $$$k$$$ distinct elements because the prefix with the length $$$p$$$ doesn't contain more than $$$k - 1$$$ distinct elements. If the prefix with the length $$$p + 1$$$ still contains less than $$$k$$$ distinct numbers, let's replace the remaining digits ($$$d_{p + 2}$$$, $$$d_{p + 3}$$$, etc) with $$$0$$$. Otherwise, we can replace them with the minimum digit that occurs in the prefix with the length $$$p + 1$$$ (it may be $$$0$$$).
3. Suppose the considered prefix contains exactly $$$k$$$ distinct digits. So let's find the minimum digit that occurs in the prefix with the length $$$p$$$ and is greater than $$$d_{p + 1}$$$. If such digit exists, let's replace $$$d_{p + 1}$$$ with it, and all following digits with the minimum digit that occurs in the prefix with the length $$$p + 1$$$. Otherwise, the element $$$d_{p + 1}$$$ cannot be increased.
The converted by the procedure $$$n$$$ is the answer.