C. Double Lexicographically Minimum
greedy; strings
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\).
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"".