CF600C Make Palindrome

如果一个字符串从左到右和从右到左读都是一样的，我们称之为回文串。例如 "kazak"、"oo"、"r" 和 "mikhailrubinchikkihcniburliahkim" 都是回文串，而 "abb" 和 "ij" 不是。 给你一个由小写拉丁字母组成的字符串 $s$。每次你可以选择字符串中的任意一个位置，将该位置的字母改成任意其他小写字母。因此，每次更改后字符串的长度不会改变。最开始你可以对 $s$ 进行若干次这样的修改。然后，你可以对字符串中的字母进行任意排序（即任意打乱顺序），排列的过程不计为更改。 你需要通过最少的字母更改操作，将原字符串变为一个回文串。如果有多种方法能做到操作次数最少，你还需要输出字典序（按字母顺序）最小的那个回文串。换句话说，首先要最小化修改次数，然后最小化最终的回文串的字典序。

输入仅一行，包含字符串 $s$（$1 \leq |s| \leq 2 \cdot 10^{5}$），字符串只包含小写拉丁字母。

输出一个经过最少修改且字典序最小的回文串。

由 ChatGPT 5 翻译