1735C.md (2296B)
1 Source: https://codeforces.com/problemset/problem/1735/C 2 3 C. Phase Shift 4 5 time limit per test 6 7 3 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 There was a string $s$ which was supposed to be encrypted. For this reason, all $26$ lowercase English letters were arranged in a circle in some order, afterwards, each letter in $s$ was replaced with the one that follows in clockwise order, in that way the string $t$ was obtained. 22 23 You are given a string $t$. Determine the lexicographically smallest string $s$ that could be a prototype of the given string $t$. 24 25 A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if: 26 27 * in the first position where $a$ and $b$ differ, the string $a$ has a letter, that appears earlier in the alphabet than the corresponding letter in $b$. 28 29 Input 30 31 The first line of the input contains a single integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases. The description of test cases follows. 32 33 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the string $t$. 34 35 The next line contains the string $t$ of the length $n$, containing lowercase English letters. 36 37 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output a single line containing the lexicographically smallest string $s$ which could be a prototype of $t$. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 1 51 52 a 53 54 2 55 56 ba 57 58 10 59 60 codeforces 61 62 26 63 64 abcdefghijklmnopqrstuvwxyz 65 66 26 67 68 abcdefghijklmnopqrstuvwxzy 69 ``` 70 71 Output 72 73 ``` 74 b 75 ac 76 abcdebfadg 77 bcdefghijklmnopqrstuvwxyza 78 bcdefghijklmnopqrstuvwxyaz 79 ``` 80 81 Note 82 83 In the first test case, we couldn't have the string "a", since the letter a would transit to itself. Lexicographically the second string "b" is suitable as an answer. 84 85 In the second test case, the string "aa" is not suitable, since a would transit to itself. "ab" is not suitable, since the circle would be closed with $2$ letters, but it must contain all $26$. The next string "ac" is suitable. 86 87 Below you can see the schemes for the first three test cases. The non-involved letters are skipped, they can be arbitrary placed in the gaps. 88 89 