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:
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$$$.
12aaababbabcaabbaabbbaaabbabbbabbbbabbcceagaffcaba
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$$$.
The lexicographical minimum of $$$t_{\mathrm{max}}$$$ over all cases is "aba".
Name |
---|