分数: 1600 点
问题陈述
字符串称为 美丽的字符串 当且仅当满足以下条件:
- 每个字符都是
A,B,或C. - 没有两个相邻的字符是相同的。
例如, AB 和 BCAC 是美丽的字符串,而 BB 和 CBAAC 不是。
给你一根美丽的绳子 S。在此字符串上,您可以重复执行以下操作。
- 操作:交换两个相邻字符 S。在这里, 交换后 S 一定仍然是一个漂亮的字符串。
找到按字典顺序排列的最小字符串 S 可以成为。
T 给出了测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 10^5
- S 是一个漂亮的字符串。
- 1\leq |S|\leq 10^6
- 总和 |S| 单个输入中的所有测试用例最多 10^6.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
S
输出
打印 T 行。的 i- 第行应包含按字典顺序排列的最小字符串 S 可以成为 i- 第一个测试用例。
示例输入 1
8 CAB ACBCB B AC BACBA BABABA ABCBCAC CBABACABCBABABC
示例输出 1
ABC ABCBC B AC ABABC BABABA ABCACBC ABABACBCACBCBAB
对于第一个和第二个测试用例,这里有一种可能的方法来按字典顺序最小化 S:
CAB→ACB→ABCACBCB→CABCB→CBACB→BCACB→BCABC→BACBC→ABCBC