Codeforces Round 862 (Div. 2) |
---|
Закончено |
Дана строка $$$s$$$. Можно ровно один раз применить к строке такую операцию: выбрать индекс $$$i$$$ и переставить символ $$$s_i$$$ в начало строки (удалив его на старой позиции). Например, если к строке «abaacd» применить операцию с индексом $$$i=4$$$ в нумерации с $$$1$$$, то получится строка «aabacd». Какую лексикографически минимальную$$$^{\dagger}$$$ строку можно получить одной такой операцией?
$$$^{\dagger}$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$ такой же длины, если и только если выполняется следующее:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — длину строки.
Вторая строка каждого набора содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$10 ^ 5$$$.
Для каждого набора входных данных в отдельной строке выведите лексикографически минимальную строку, которую можно получить после применения одной операции из условия к исходной строке ровно один раз.
43cba4acac5abbcb4aaba
acb aacc abbcb aaab
В первом наборе нужно переместить последний символ в начало.
Во втором наборе входных данных нужно перенести в начало вторую букву «a».
В третьем наборе нужно применить операцию с $$$i=1$$$, тогда строка не изменится.
Название |
---|