2050D.md (1617B)
1 Source: https://codeforces.com/problemset/problem/2050/D 2 3 D. Digital string maximization 4 5 time limit per test 6 7 2 seconds 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 are given a string $s$, consisting of digits from $0$ to $9$. In one operation, you can pick any digit in this string, except for $0$ or the leftmost digit, decrease it by $1$, and then swap it with the digit left to the picked. 22 23 For example, in one operation from the string $1023$, you can get $1103$ or $1022$. 24 25 Find the lexicographically maximum string you can obtain after any number of operations. 26 27 Input 28 29 The first line of the input consists of an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 Each test case consists of a single line consisting of a digital string $s$ ($1 \le |s| \le 2\cdot 10^5$), where $|s|$ denotes the length of $s$. The string does not contain leading zeroes. 32 33 It is guaranteed that the sum of $|s|$ of all test cases doesn't exceed $2\cdot 10^5$. 34 35 Output 36 37 For each test case, print the answer on a separate line. 38 39 Example 40 41 Input 42 43 ``` 44 6 45 46 19 47 48 1709 49 50 11555 51 52 51476 53 54 9876543210 55 56 5891917899 57 ``` 58 59 Output 60 61 ``` 62 81 63 6710 64 33311 65 55431 66 9876543210 67 7875567711 68 ``` 69 70 Note 71 72 In the first example, the following sequence of operations is suitable: $19 \rightarrow 81$. 73 74 In the second example, the following sequence of operations is suitable: $1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710$. 75 76 In the fourth example, the following sequence of operations is suitable: $51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431$.