1730C.md (1814B)
1 Source: https://codeforces.com/problemset/problem/1730/C 2 3 C. Minimum Notation 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have a string $s$ consisting of digits from $0$ to $9$ inclusive. You can perform the following operation any (possibly zero) number of times: 22 23 * You can choose a position $i$ and delete a digit $d$ on the $i$-th position. Then insert the digit $\min{(d + 1, 9)}$ on any position (at the beginning, at the end or in between any two adjacent digits). 24 25 What is the lexicographically smallest string you can get by performing these operations? 26 27 A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if the following holds: 28 29 * in the first position where $a$ and $b$ differ, the string $a$ has a smaller digit than the corresponding digit in $b$. 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the test cases follow. 34 35 Each test case consists of a single line that contains one string $s$ ($1 \le |s| \le 2 \cdot 10^5$) — the string consisting of digits. Please note that $s$ is just a string consisting of digits, so leading zeros are allowed. 36 37 It is guaranteed that the sum of lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 Print a single string — the minimum string that is possible to obtain. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 04829 51 52 9 53 54 01 55 56 314752277691991 57 ``` 58 59 Output 60 61 ``` 62 02599 63 9 64 01 65 111334567888999 66 ``` 67 68 Note 69 70 In the first test case: 71 72 * Delete $8$ and insert $9$ at the end of the notation. The resulting notation is $04299$. 73 * Delete $4$ and insert $5$ in the $3$-rd position of the notation. The resulting notation is $02599$. 74 75 Nothing needs to be done in the second and third test cases.