← 返回题目列表

AtCoder · agc066_f

F. 美丽的绳子

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

分数: 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 → ABC
  • ACBCB → CABCB → CBACB → BCACB → BCABC → BACBC → ABCBC