← 返回题目列表

Codeforces · 1063/A

A. 哦那些回文

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

如果从左到右和从右到左读取相同的非空字符串,则称为回文字符串。例如,“abcba”、“a”和“abba”是回文,而“abab”和“xy”则不是。

如果一个字符串可以通过从该字符串的开头和结尾删除一些(可能为零)个字符来获得,则该字符串称为另一个字符串的子字符串。例如,“abc”、“ab”和“c”是字符串“abc”的子字符串,而“ac”和“d”则不是。

让我们将字符串的回文计数定义为其回文子字符串的数量。例如,字符串“aaa”的回文数为$$$6$$$,因为它的所有子串都是回文;字符串“abc”的回文数为$$$3$$$,因为只有长度为$$$1$$$的子串是回文。

给你一个字符串$$$s$$$。您可以任意重新排列其字符。您的目标是获得回文计数最大可能值的字符串。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 字符串 $$$s$$$ 的长度。

第二行包含字符串 $$$s$$$,该字符串恰好由 $$$n$$$ 拉丁字母小写字符组成。

输出

打印字符串 $$$t$$$,它由与字符串 $$$s$$$ 相同的字符集组成(并且每个字符出现的次数完全相同)。此外,$$$t$$$ 应该具有所有此类字符串中回文计数的最大可能值。

如果有多个这样的字符串,则打印其中任何一个。

示例

输入 #1

5
oolol

输出 #1

ololo

输入 #2

16
gagadbcgghhchbdf

输出 #2

abccbaghghghgdfd

注意

在第一个示例中,字符串“ololo”具有 $$$9$$$ 回文子字符串:“o”、“l”、“o”、“l”、“o”、“olo”、“lol”、“olo”、“ololo”。请注意,即使某些子字符串重合,它们也会按照它们在结果字符串中出现的次数进行计数。

在第二个示例中,字符串“abccbaghghghgdfd”的回文计数为 $$$29$$$。