Problem Description

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

Input Format

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 Format

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

10
bbaaabcaba

38

Hint

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