← 返回题目列表

Codeforces · 1913/F

F. 回文问题

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

给定一个字符串 $$$s$$$,长度为 $$$n$$$,由小写拉丁字母组成。

您最多可以将字符串中的一个字符替换为任意小写拉丁字母。

打印可以从原始字符串中获得的按字典顺序排列的最小字符串,并且包含最大数量的回文作为子字符串。请注意,如果回文作为子字符串出现多次,则按其出现的次数进行计数。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 包含一个在字母表中出现早于 $$$b$$$ 中相应字母的字母。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 字符串中的字符数。

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

输出

在第一行中,打印一个整数——使用语句中描述的操作最多一次可以获得的回文子串的最大数量。

在第二行中,打印可以从 $$$s$$$ 获得的字符串,并且该字符串具有最大可能的回文子串数。如果有多个答案,请打印字典顺序最小的一个。

示例

输入 #1

5
aabaa

输出 #1

15
aaaaa

输入 #2

5
aaaaa

输出 #2

15
aaaaa

输入 #3

4
awoo

输出 #3

7
aooo