407334: GYM102766 H Singhal and String

If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.

Singhal has a string $$$S$$$ consisting of lowercase English letters. He wants to form lexicographical smallest string by applying a operation atmost once.

Operation is —

Choose three distinct indices $$$i_1,i_2,i_3$$$ such that $$$1\leq i_i<i_2<i_3 \leq |S|$$$, where $$$|S|$$$ is the length of string and perform cyclic right shift on these indices.

If value at $$$i_1,i_2,i_3$$$ is $$$s_1,s_2,s_3$$$, then after performing right cyclic shift on these indices, value at indices will change to $$$i_2\to s_1 , i_3\to s_2 , i_1\to s_3$$$.

Example - $$$S = $$$ "codedigger". Chosen indices is $$$1,2,3$$$ then resultant string will be $$$S = $$$ "dcoedigger".

A string a is lexicographical smaller than a string b if and only if one of the following holds:

• a is a prefix of b, but a$$$\neq$$$b;
• 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.

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains a string $$$S(1\leq |S| \leq 10^5)$$$ consisting of lowercase English letters. $$$|S|$$$ is the length of the string.

It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.

Print $$$t$$$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.

5
aba
abc
acb
codedigger
codealittle

aab
abc
acb
cddoeigger
acdeolittle

In the first query, apply right cyclic shift on indices $$$1,2,3$$$ to get the smallest possible string $$$S=$$$ aab.

In the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.