[Solution] Phase Shift solution codeforces

Phase Shift solution codeforces – There was a string 𝑠s which was supposed to be encrypted. For this reason, all 2626 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.

You are given a string 𝑡t. Determine the lexicographically smallest string 𝑠s that could be a prototype of the given string 𝑡t.

A string 𝑎a is lexicographically smaller than a string 𝑏b of the same length if and only if:

  • 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.

[Solution] Phase Shift solution codeforces

The first line of the input contains a single integer 𝑡t (1𝑡31041≤t≤3⋅104) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer 𝑛n (1𝑛1051≤n≤105) — the length of the string 𝑡t.

The next line contains the string 𝑡t of the length 𝑛n, containing lowercase English letters.

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 21052⋅105.

[Solution] Phase Shift solution codeforces

For each test case, output a single line containing the lexicographically smallest string 𝑠s which could be a prototype of 𝑡t.

Example

input

Copy
5
1
a
2
ba
10

[Solution] Phase Shift solution codeforces

26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy

output

Copy
b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz

[Solution] Phase Shift solution codeforces

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.

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 22 letters, but it must contain all 2626. The next string “ac” is suitable.

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.

[Solution] Phase Shift solution codeforces

 

For Solution

“Click Here”

Leave a Comment