← 返回题目列表

AtCoder · arc209_b

B. 最小化偶数回文

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

分数: 700 点

问题陈述

对于字符串 s 由小写英文字母组成,令 f(s) 表示子串的数量 s 是偶数长度的回文。更准确地说, f(s) 是整数对的数量 l, r 满足以下所有条件:

  • 1 \leq l \leq r \leq |s|.
  • r - l + 1 是偶数。
  • s_l s_{l+1} \cdots s_{r} 是一个回文。

给定一个字符串 S 由小写英文字母组成,输出一串 S' 通过重新排列字符获得 S 这样 f(S') 被最小化。

你被给予 T 测试用例。解决它们中的每一个。

约束

  • 1 \le T \le 10^5
  • 2 \le |S| \le 2 \times 10^5
  • S 由小写英文字母组成。
  • 总和 |S| 所有测试用例最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

S

输出

输出 T 行。

的 i- 第行应包含一个字符串 S' 通过重新排列字符获得 S 在 i- 第一个测试用例 f(S') 被最小化。如果有多个这样的 S',其中任何一个都将被认为是正确的。


示例输入 1

3
see
xxxxxy
abracadabra

示例输出 1

ese
xxxyxx
abracadabra

对于第一个测试用例,字符串 S' 通过重新排列字符获得 S 是 see, ese,和 ees。其中,仅 ese 最小化 f(S'),所以输出它。

对于第二个测试用例,例如,输出 xxyxxx 也将被认为是正确的。