#P3067. Hyperdrome
Hyperdrome
Hyperdrome
题目背景
来自银河系各地的侏儒参加 Hypergnome 星球上的运动会。其中最受欢迎的项目是 Hyperdrome。
题目描述
裁判给出一个字符串 ,所有选手要尽快数出其中的 Hyperdrome 子串。若一个子串中的字符可以重新排列成回文串,这个子串就是 Hyperdrome。
子串由 中第 到第 个字符构成,包含两端,满足 。按起点和终点计数,即使内容相同,只要位置不同就分别计数。
长度为 的字符串 是回文串,当且仅当每个位置 都满足 。
侏儒使用英文大写和小写字母。大小写字母视为不同字符。请帮助选手求出 Hyperdrome 子串的数量。
输入格式
第一行包含一个整数 (),表示字符串长度。第二行是长度为 的字符串 。
输出格式
输出一行一个整数,表示 Hyperdrome 子串的数量。
样例
3
aaa
6
7
abadaba
12
3
aAA
5
样例说明
- 第一组有 个符合条件的子串,区间分别为 、、、、、。
- 第二组有 个符合条件的子串,包括 个单字符子串,以及区间 、、、、。
- 第三组的区间是 、、、、。区间 中的
aAA可以重排为回文串AaA。