CF1913F.Palindromic Problem

You are given a string $s$ of length $n$, consisting of lowercase Latin letters.

You are allowed to replace at most one character in the string with an arbitrary lowercase Latin letter.

Print the lexicographically minimal string that can be obtained from the original string and contains the maximum number of palindromes as substrings. Note that if a palindrome appears more than once as a substring, it is counted the same number of times it appears.

The string $a$ is lexicographically smaller than the string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ are different, the string $a$ contains a letter that appears earlier in the alphabet than the corresponding letter in $b$.

给你一个长度为 $n$ 的字符串 $s$，它仅由小写拉丁字母组成。

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

请输出一个字典序最小的字符串，该字符串由原字符串经过至多一次字符替换得到，且其作为子串所包含的回文串数量达到最大。注意：如果某个回文串在字符串中多次出现，则每次出现均单独计数。

当且仅当满足以下条件之一时，字符串 $a$ 的字典序小于字符串 $b$：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中的字符在字母表中位于 $b$ 中对应字符之前。

The first line contains one integer $n$ ($1 \leq n \leq 3 \cdot 10^5$) — the number of characters in the string.

The second line contains the string $s$ itself, consisting of exactly $n$ lowercase Latin letters.

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

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

In the first line, print one integer — the maximum number of palindromic substrings that can be obtained using the operation described in the statement at most once.

In the second line, print the string that can be obtained from $s$ and has the maximum possible number of palindromic substrings. If there are multiple answers, print the lexicographically smallest one.

第一行，输出一个整数——即最多执行一次题目所述操作后，所能得到的回文子串的最大数量。

第二行，输出由字符串 $s$ 经过该操作后所得、且具有最多可能回文子串的字符串。若存在多个满足条件的答案，请输出字典序最小的一个。