切开字符串

题目描述

Pear 有一个字符串，不过他希望把它切成两段，这是一个长度为 n 的字符串。

Pear 希望选择一个位置，把字符串不重复不遗漏地切成两段，长度分别是 t 和 n-t（这两段都必须非空）。

Pear 用如下方式评估切割的方案：

定义“正回文子串”为：长度为奇数的回文子串。

设切成的两段字符串中，前一段中有 A 个不相同的正回文子串，后一段中有 B 个不相同的非正回文子串，则该方案的得分为 A * B。

注意，后一段中的 B 表示的是：“…非正回文…”，而不是: “…正回文…”。

那么所有的切割方案中，A * B 的最大值是多少呢？

输入格式

输入第一行一个正整数 n。

接下来一行一个字符串，长度为 n，该字符串仅包含小写英文字母。

输出格式

一行一个正整数，表示所求的 A * B 的最大值。

样例输入

10

bbaaabcaba

样例输出

38

数据范围

对于 20% 的数据，N ≤ 100

对于 40% 的数据，N ≤ 1000

对于 100% 的数据，N ≤ 100000