Palindromic Problem
Contest: Educational Codeforces Round 160 (Rated for Div. 2)
Difficulty rating: 2800
Tags: binary search, data structures, hashing, string suffix structures, strings

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$$$.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
5
aabaa

Example output:
15
aaaaa

Example input:
5
aaaaa

Example output:
15
aaaaa

Editorial:
Let's recall the algorithm for counting the number of palindromes in a string. For each position, we can calculate the longest odd and even palindromes with centers at that position (the right one for even). Then sum up all the values.
If we forget about the complexity, we can consider the following algorithm for solving the full problem. Iterate over the index of the change and the new letter. Make the change, count the number of palindromes, and update the answer. In case of equality, choose the lexicographically minimal change.
Let's keep the first step and optimize the rest. It won't be possible to count the number of palindromes from scratch for every change, so let's try to calculate how much their number will change from the original. It's also not feasible to compare all strings lexicographically naively, so we have to come up with a faster way to compare.
Let's fix the change position $$$i$$$. Which of the longest palindromes change? If for some center $$$j$$$, the longest palindrome included $$$i$$$, then we definitely know its new length. Due to the change at $$$i$$$, the longest palindrome will stop at $$$i$$$. If the longest palindrome did not reach $$$i$$$, it will not change. And only if it stopped at $$$i$$$, it can become longer, and we don't know by how much yet. But for each center $$$j$$$ and the parity of the palindrome, there are only positions to the left and to the right where it stops. So, in total, we will need to make $$$O(n)$$$ such checks.
How to take into account the palindromes that become shorter? We need to calculate the sum of the differences for all palindromes that include $$$i$$$. For an odd palindrome, this change looks like this: $$$[\dots, 0, -1, -2, -3, -4, -3, -2, -1, 0, \dots]$$$, where $$$-4$$$ is the center of the palindrome, and the values show the difference in the number of palindromes for each position of the string. For an even palindrome: $$$[\dots, 0, -1, -2, -3, -3, -2, -1, 0, \dots]$$$. To calculate the sum at each position, we can pre-calculate a difference array based on these values.
The difference array usually implies first-order changes: write $$$+x$$$ at $$$l$$$, write $$$-x$$$ at $$$r+1$$$, then collect the prefix sum to get $$$[\dots, 0, x, x, \dots, x, 0, \dots]$$$. But we can also record second-order changes. For the odd construction, we will write as follows. Let the length of the palindrome be $$$\mathit{len}$$$, and the center be $$$i$$$. Then:
• $$$\mathit{dt}[i - \mathit{len} + 1] \mathrel{{+}{=}} 1$$$;
• $$$\mathit{dt}[i + 1] \mathrel{{-}{=}} 2$$$;
• $$$\mathit{dt}[i + \mathit{len} + 1] \mathrel{{+}{=}} 1$$$.
Then iterate from left to right, maintaining two variables. The current change and the current value. At each $$$i$$$, add $$$\mathit{dt}[i]$$$ to the change, add the change to the value, and save the value to some array.
For the even case, it is built similarly. It is easy to see that such changes can be made at the same time. Basically the same as the regular difference array.
Now, in each position, the total decrease in the length of the palindromes passing through that position is recorded. The answer will decrease by almost this amount. The only difference is the odd-length palindromes with a center at this position. They will not change at all, and we accidentally subtracted them. Thus, let's save the longest odd palindrome for each position in advance and add it back.
Let's learn how to calculate the longest palindromes for each center. Yes, there is the Manacher's algorithm for a static string. We can use it for counting at the very beginning, but it's not really necessary. Instead, let's learn to count palindromes using suffix structures. In particular, with a suffix array.
It is known that with an additional sparse table, we can query the longest common prefix of two suffixes in $$$O(1)$$$ with pre-calculation in $$$O(n \log n)$$$. Let's build a suffix array on the string $$$s + \# + \mathit{rev}(s) + \$$$$. Then we can query the LCP of both suffixes and reverse prefixes. Then the longest odd palindrome with center at $$$i$$$ is LCP($$$s[i..n]$$$, $$$\mathit{rev}$$$($$$s[1..i]$$$)). The even one is LCP($$$s[i..n]$$$, $$$\mathit{rev}$$$($$$s[1..i-1]$$$)).
So, we can count the palindromes at the very beginning with $$$O(n \log n)$$$ pre-calculation and $$$O(n)$$$ extra calculations.
The following task remains. For each position, the centers of the palindromes that reach it are known. For each such center, we need to be able to recalculate how much longer the palindrome will become after changing the letter at that position.
Obviously, even the new letter may still not match the letter on the other side. If it does match, we would like to know how many letters further match the opposite ones in the original string. And we already have a tool for this. It's still a simple LCP query on the suffix to the right of the right letter and the reverse prefix to the left of the left letter.
Now we have everything necessary to recalculate the number of palindromes.
If the new count is greater than the current maximum, we will simply update the answer. If it is equal, we need to check the lexicographic order. The following check works:
• if one change increased the original letter, and the other decreased it, then the second one will definitely produce a smaller string;
• if both changes decreased it, then the more left one will produce a smaller string; if both are in the same position, the smaller letter will produce a smaller string;
• if both changes increased it, then the more right one will produce a smaller string; if both are in the same position, the smaller letter will produce a smaller string.
All these checks can be performed in $$$O(1)$$$.
Overall complexity: $$$O(n \log n + n \cdot |\mathit{AL}|)$$$.