A7677. Adjacent Distinct String
编程题
普及/提高-
知识点
题目描述
给你一个由小写英文字母组成的字符串 $S$。
判断是否可以重新排列 $S$ 的字符，使得任意两个相邻字符均不相同；如果可以，请找出其中一种满足条件的排列。
你将得到 $T$ 组测试数据；请对每组数据求解。
判断是否可以重新排列 $S$ 的字符，使得任意两个相邻字符均不相同；如果可以，请找出其中一种满足条件的排列。
你将得到 $T$ 组测试数据；请对每组数据求解。
输入格式
输入从标准输入给出，格式如下：
> $T$
> $\text{case}_1$
> $\text{case}_2$
> $\vdots$
> $\text{case}_T$
第 $i$ 个 $(1 \le i \le T)$ 测试用例 $\text{case}_i$ 的格式如下：
> $S$
> $T$
> $\text{case}_1$
> $\text{case}_2$
> $\vdots$
> $\text{case}_T$
第 $i$ 个 $(1 \le i \le T)$ 测试用例 $\text{case}_i$ 的格式如下：
> $S$
输出格式
按测试用例的顺序输出答案，每个答案之间用换行符分隔。
对于每个测试用例，如果无法重排字符串 $S$ 使得任意两个相邻字符均不相同，则输出
否则（即可以重排），设 $S'$ 为满足条件的一种重排结果，并按以下格式输出：
> Yes
> $S'$
若字符串 $S$ 存在多种合法重排方式，则输出任意一种均可。
对于每个测试用例，如果无法重排字符串 $S$ 使得任意两个相邻字符均不相同，则输出
No。否则（即可以重排），设 $S'$ 为满足条件的一种重排结果，并按以下格式输出：
> Yes
> $S'$
若字符串 $S$ 存在多种合法重排方式，则输出任意一种均可。
输入输出样例
输入 #1
3 aiiw doodoo aabbababcacababaaba
输出 #1
Yes iwai No Yes ababacabababacababa
说明/提示
**样例 1 解释：**
考虑第一个测试用例。
其他正确的输出还包括
### 约束条件
* $1 \le T \le 3 \times 10^5$
* $S$ 是一个长度在 $1$ 到 $10^6$（含）之间的字符串，仅由小写英文字母组成。
* 所有测试用例中 $S$ 的总长度不超过 $10^6$。
考虑第一个测试用例。
iwai 是 aiiw 的一个重排，且其中任意两个相邻字符均不相同。因此，输出 iwai 是正确的。其他正确的输出还包括
wiai 和 iawi。### 约束条件
* $1 \le T \le 3 \times 10^5$
* $S$ 是一个长度在 $1$ 到 $10^6$（含）之间的字符串，仅由小写英文字母组成。
* 所有测试用例中 $S$ 的总长度不超过 $10^6$。