/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
英小文字からなる文字列 S が与えられます。
S の各文字を並び替えることでどの隣り合う 2 文字も異なるようにすることが可能か判定し、可能な場合はそのような並び替えを一つ求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 3\times 10^5
- S は英小文字からなる長さ 1 以上 10^6 以下の文字列
- 全てのテストケースにおける S の長さの総和は 10^6 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
i 番目 (1\le i\le T) のテストケース \text{case}_i は以下の形式で与えられる。
S
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、どの隣り合う 2 文字も異なるように S を並び替えることが不可能な場合は No を出力せよ。
可能な場合はそのような並び替えを S' として以下の形式で出力せよ。
Yes S'
条件を満たす S の並び替え方が複数存在する場合、どれを出力しても正答となる。
入力例 1
3 aiiw doodoo aabbababcacababaaba
出力例 1
Yes iwai No Yes ababacabababacababa
1 番目のテストケースについて考えます。
iwai は aiiw を並び替えてできる文字列で、どの隣接する 2 文字も異なります。したがって、iwai を出力すると正答となります。
この他にも、wiai や iawi などを出力しても正答となります。
Score : 400 points
Problem Statement
You are given a string S consisting of lowercase English letters.
Determine whether it is possible to rearrange the characters of S so that no two adjacent characters are the same, and if so, find one such rearrangement.
You are given T test cases; solve each.
Constraints
- 1 \le T \le 3 \times 10^5
- S is a string of length between 1 and 10^6, inclusive, consisting of lowercase English letters.
- The total length of S across all test cases is at most 10^6.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
The i-th (1 \le i \le T) test case \text{case}_i is given in the following format:
S
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, if it is impossible to rearrange S so that no two adjacent characters are the same, output No.
If it is possible, let S' be such a rearrangement and output in the following format:
Yes S'
If there are multiple valid rearrangements of S, any of them will be accepted.
Sample Input 1
3 aiiw doodoo aabbababcacababaaba
Sample Output 1
Yes iwai No Yes ababacabababacababa
Consider the first test case.
iwai is a rearrangement of aiiw in which no two adjacent characters are the same. Thus, outputting iwai is correct.
Other correct outputs include wiai and iawi.