← 返回题目列表

AtCoder · abc459_d

D. 相邻的不同字符串

中文机器翻译题面 查看原题

分数: 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.