P8631 [Lanqiao Cup 2015 National AC] Cut the String

Pear has a string, and he wants to cut it into two parts. The string has length $N$ ($\le 10^5$). Pear wants to choose a position and cut the string into two non-overlapping parts without repetition or omission, with lengths $t$ and $N-t$ (both parts must be non-empty). Pear evaluates a cutting plan as follows: Define an “odd palindrome substring” as a palindrome substring with odd length. Suppose that in the two resulting substrings, the first part contains $A$ distinct odd palindrome substrings, and the second part contains $B$ distinct non-odd-palindrome substrings. Then the score of this plan is $A \times B$. Note that $B$ in the second part means “... non-odd-palindrome ...”, not “... odd-palindrome ...”. Among all cutting plans, what is the maximum value of $A \times B$?

The first line contains a positive integer $N$ ($\le 10^5$). The next line contains a string of length $N$, consisting only of lowercase English letters.

Output one positive integer, representing the maximum value of $A \times B$.

For $20\%$ of the testdata, $N \le 100$. For $40\%$ of the testdata, $N \le 1000$. For $100\%$ of the testdata, $N \le 10^5$. Time limit: 1 second, 512 MB. Lanqiao Cup 2015, 6th National Contest. Translated by ChatGPT 5