/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
英小文字からなる文字列 s に対し、s の部分文字列であって、偶数長の回文であるものの個数を f(s) で表します。より厳密には、f(s) は以下の条件を全て満たす整数 l, r の組の個数です。
- 1 \leq l \leq r \leq |s|
- r - l + 1 は偶数
- s_l s_{l+1} \cdots s_{r} は回文
英小文字からなる文字列 S が与えられるので、S の文字を並べ替えて得られる文字列 S' のうち、f(S') が最小となるものを 1 つ出力してください。
T 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- 1 \le T \le 10^5
- 2 \le |S| \le 2 \times 10^5
- S は英小文字からなる
- 全てのテストケースにおける |S| の総和は 2 \times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
S
出力
T 行出力せよ。
i 行目には i 番目のテストケースについて、S の文字を並べ替えて得られる文字列 S' のうち、f(S') が最小となるものを 1 つ出力せよ。そのような S' が複数ある場合は、どれを出力しても正答となる。
入力例 1
3 see xxxxxy abracadabra
出力例 1
ese xxxyxx abracadabra
1 番目のテストケースについて、S の文字を並べ替えて得られる文字列 S' として see, ese, ees が考えられますが、このうち f(S') が最小となるものは ese のみなので、これを出力します。
2 番目のテストケースについて、例えば xxyxxx と出力しても正答となります。
Score : 700 points
Problem Statement
For a string s consisting of lowercase English letters, let f(s) denote the number of substrings of s that are palindromes of even length. More precisely, f(s) is the number of pairs of integers l, r that satisfy all of the following conditions:
- 1 \leq l \leq r \leq |s|.
- r - l + 1 is even.
- s_l s_{l+1} \cdots s_{r} is a palindrome.
Given a string S consisting of lowercase English letters, output one string S' obtained by rearranging the characters of S such that f(S') is minimized.
You are given T test cases. Solve each of them.
Constraints
- 1 \le T \le 10^5
- 2 \le |S| \le 2 \times 10^5
- S consists of lowercase English letters.
- The sum of |S| over all test cases is at most 2 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
S
Output
Output T lines.
The i-th line should contain one string S' obtained by rearranging the characters of S in the i-th test case such that f(S') is minimized. If there are multiple such S', any of them will be considered correct.
Sample Input 1
3 see xxxxxy abracadabra
Sample Output 1
ese xxxyxx abracadabra
For the first test case, the strings S' obtained by rearranging the characters of S are see, ese, and ees. Among these, only ese minimizes f(S'), so output it.
For the second test case, for example, outputting xxyxxx will also be considered correct.