codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/703a6d4597b66d41db894d2cfc0e317b22cf40c3.png)