分数: 400 点
问题陈述
给你一个字符串 S 由小写英文字母组成。
判断是否可以重新排列字符 S 使得没有两个相邻字符是相同的,如果是,则找到一个这样的重新排列。
你被给予 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-th (1 \le i \le T) 测试用例 \text{case}_i 按以下格式给出:
S
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,如果无法重新排列 S 使得没有两个相邻字符相同,输出 No.
如果可能的话,让 S' 进行这样的重新排列并按以下格式输出:
Yes S'
如果存在多个有效的重新排列 S,其中任何一个都会被接受。
示例输入 1
3 aiiw doodoo aabbababcacababaaba
示例输出 1
Yes iwai No Yes ababacabababacababa
考虑第一个测试用例。
iwai 是以下内容的重新排列 aiiw 其中没有两个相邻字符相同。因此,输出 iwai 是正确的。
其他正确的输出包括 wiai 和 iawi.