相邻字符不同的字符串AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a string $S$ consisting of lowercase English letters.
给定一个由小写英文字母组成的字符串 $S$。AI (CI翻译)
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.
请判断是否可以重新排列 $S$ 中的字符，使得不存在两个相邻字符相同；如果可以，请找出一种这样的排列。AI (CI翻译)
You are given $T$ test cases; solve each.
给定 $T$ 个测试用例，请分别求解。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$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$.
$1 \le T \le 3 \times 10^5$$S$是一个长度在$1$到$10^6$之间（含端点）的字符串，由小写英文字母组成。- 所有测试用例中的
$S$的总长度不超过$10^6$。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_TT
\text{case}_1
\text{case}_2
\vdots
\text{case}_TThe $i$-th $(1 \le i \le T)$ test case $\text{case}_i$ is given in the following format:
第 $i$ 个 $(1 \le i \le T)$ 测试用例 $\text{case}_i$ 按以下格式给出：AI (CI翻译)
SSOutput
输出格式
AI (CI翻译)Output the answers for the test cases in order, separated by newlines.
按顺序输出各个测试用例的答案，每个答案之间用换行分隔。AI (CI翻译)
For each test case, if it is impossible to rearrange $S$ so that no two adjacent characters are the same, output No.
对于每个测试用例，如果无法重新排列 $S$，使得不存在两个相邻字符相同，则输出 No。AI (CI翻译)
If it is possible, let $S'$ be such a rearrangement and output in the following format:
如果可以，设 $S'$ 为这样的一种排列，并按以下格式输出：AI (CI翻译)
Yes
S'Yes
S'If there are multiple valid rearrangements of $S$, any of them will be accepted.
如果存在多个满足条件的排列，输出其中任意一个即可。AI (CI翻译)
样例
3
aiiw
doodoo
aabbababcacababaaba
Yes
iwai
No
Yes
ababacabababacababa
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。