#36 「 好的回文串 」

统计

如果把一个字符串从头到尾翻转后和原字符串相等,我们称之为回文串,比如"aabaa"、"())("、"2017102"。

如果一个字符串存在两个出现过的字母出现的次数相等,我们称之为好的字符串。

现在给一个由小写字母组成的字符串,问在这个字符串的所有连续子串中,好的回文串有多少个。(两个相同的回文串出现在不同位置算多次)。

输入格式

一行一个小写字母组成的字符串。

输出格式

一行一个整数,表示答案。

样例数据

input

abcbaabcba

output

6

样例解释

abcba s[1..5] a,b出现次数相等

baab s[4..7] a,b出现次数相等

cbaabc s[3..8] a,b出现次数相等

bcbaabcb s[2..9] a,c出现次数相等

abcbaabcba s[1..10] a,b出现次数相等

abcba s[6..10] a,b出现次数相等

数据规模与约定

len表示字符串长度。

$1\le len \le 10^4$。

时间限制:1s

空间限制:512MB

Author: zrt