← 返回题目列表

Codeforces · 600/C

C. 制作回文

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

如果一个字符串从左到右和从右到左读取相同,则称为回文。例如,“kazak”、“oo”、“r”和“mikhailrubinchikkihcniburliahkim”是回文,但字符串“abb”和“ij”不是。

给定一个由小写拉丁字母组成的字符串 s。您可以立即选择字符串中的任何位置并将该位置的字母更改为任何其他小写字母。因此每次更改后字符串的长度都不会改变。首先你可以改变s中的一些字母。然后您可以根据需要排列字母的顺序。排列不算作更改。

您应该获得具有最少变化次数的回文。如果有多种方法可以做到这一点,您应该获得按字典顺序(按字母顺序)最小的回文。因此,首先应该最小化更改的数量,然后按字典顺序最小化回文。

输入

唯一一行包含仅由小写拉丁字母组成的字符串 s (1 ≤ |s| ≤ 2·105)。

输出

打印可以通过最少的更改次数获得的字典顺序最小的回文。

示例

输入 #1

aabc

输出 #1

abba

输入 #2

aabcd

输出 #2

abcba