Double Lexicographically Minimum

题意翻译

给你一个字符串 $s$，你可以重排 $s$ 中的字母而得到字符串 $t$。定义 $t_{\max}$ 为 $t$ 和 $\operatorname{rev}(t)$（$\operatorname{rev}(t)$ 表示把 $t$ 前后翻转得到的字符串）中字典序较大者。现在你需要让 $t_{\max}$ 的字典序最小，并输出 $t_{\max}$（而不是 $t$，所以答案是唯一的）。 $T\leqslant 10^5$，$\sum |s|\leqslant 10^5$。

题目描述

You are given a string $ s $ . You can reorder the characters to form a string $ t $ . Define $ t_{\mathrm{max}} $ to be the lexicographical maximum of $ t $ and $ t $ in reverse order. Given $ s $ determine the lexicographically minimum value of $ t_{\mathrm{max}} $ over all reorderings $ t $ of $ s $ . A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne 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 \leq t \leq 10^5 $ ) — the number of test cases. Descriptions of test cases follow. The first and only line of each test case contains a string $ s $ ( $ 1 \leq |s| \leq 10^5 $ ). $ s $ consists of only lowercase English letters. It is guaranteed that the sum of $ |s| $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print the lexicographically minimum value of $ t_{\mathrm{max}} $ over all reorderings $ t $ of $ s $ .

输入输出样例

输入样例 #1

12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba

输出样例 #1

a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba

说明

For the first test case, there is only one reordering of $ s $ , namely "a". For the second test case, there are three reorderings of $ s $ . - $ t = \mathtt{aab} $ : $ t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa} $ - $ t = \mathtt{aba} $ : $ t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba} $ - $ t = \mathtt{baa} $ : $ t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa} $ The lexicographical minimum of $ t_{\mathrm{max}} $ over all cases is "aba".

题目大意：
给定一个字符串s，你可以重新排列s中的字母以形成字符串t。定义t_max为t和t反转后的字符串中字典序较大者。现在你需要使t_max的字典序最小，并输出t_max（而不是t，所以答案是唯一的）。

输入输出数据格式：
输入格式：
第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行且唯一一行包含一个字符串s（1≤|s|≤10^5）。s仅由小写英文字母组成。
保证所有测试用例的s长度之和不超过10^5。

输出格式：
对于每个测试用例，输出在所有s的重新排列t中，t_max的字典序的最小值。

输入输出样例：
输入样例 #1
```
12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba
```
输出样例 #1
```
a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba
```
题目大意： 给定一个字符串s，你可以重新排列s中的字母以形成字符串t。定义t_max为t和t反转后的字符串中字典序较大者。现在你需要使t_max的字典序最小，并输出t_max（而不是t，所以答案是唯一的）。 输入输出数据格式： 输入格式： 第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行且唯一一行包含一个字符串s（1≤|s|≤10^5）。s仅由小写英文字母组成。 保证所有测试用例的s长度之和不超过10^5。 输出格式： 对于每个测试用例，输出在所有s的重新排列t中，t_max的字典序的最小值。 输入输出样例： 输入样例 #1 ``` 12 a aab abb abc aabb aabbb aaabb abbb abbbb abbcc eaga ffcaba ``` 输出样例 #1 ``` a aba bab bca abba abbba ababa bbab bbabb bbcca agea acffba ```