Codeforces Round 824 (Div. 2) |
---|
Закончено |
Была строка $$$s$$$, которую захотели зашифровать. Для этого взяли все $$$26$$$ строчных латинских букв, расположили их в некотором порядке по кругу, после чего заменили каждую букву в $$$s$$$ на ту, что является следующей по часовой стрелке, получив таким образом строку $$$t$$$.
Вам дали строку $$$t$$$. Определите лексикографически минимальную строку $$$s$$$, из которой могла быть получена данная строка $$$t$$$.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$ такой же длины, если и только если:
Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — количество наборов входных данных. Описание наборов входных данных следует ниже.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину строки $$$t$$$.
Следующая строка содержит строку $$$t$$$ длины $$$n$$$, состоящую из строчных букв латинского алфавита.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одну строку — лексикографически минимальную строку $$$s$$$, из которой могла получиться $$$t$$$.
51a2ba10codeforces26abcdefghijklmnopqrstuvwxyz26abcdefghijklmnopqrstuvwxzy
b ac abcdebfadg bcdefghijklmnopqrstuvwxyza bcdefghijklmnopqrstuvwxyaz
В первом наборе входных данных мы не могли иметь строку «a», поскольку тогда буква a переходила бы сама в себя, что невозможно. В качестве ответа нам подходит лексикографически вторая строка «b».
Во втором наборе нам не подходит «aa», поскольку a переходила бы в себя, и не подходит «ab», поскольку круг переходов замкнулся бы на $$$2$$$ буквах, а он должен состоять из всех $$$26$$$. Следующая строка «ac» нам подходит.
Ниже приведены схемы для первых трех наборов входных данных. В круге пропущены неучаствующие буквы, их можно расставить произвольно в пропуски.
Название |
---|