#G1105. [GESP202503 七级] 等价消除
[GESP202503 七级] 等价消除
[GESP202503 七级] 等价消除
题目描述
小 A 有一个仅包含小写英文字母的字符串 。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。
小 A 想知道 有多少子串是可以被等价消除的。
一个字符串 是 的子串,当且仅当删去 的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 。
输入格式
第一行,一个正整数 ,表示字符串 的长度。
第二行,一个仅包含小写英文字母的字符串 。
输出格式
一行,一个整数,表示答案。
样例 #1
样例输入 #1
7
aaaaabb
样例输出 #1
9
样例 #2
样例输入 #2
9
babacabab
样例输出 #2
2
数据范围
| 测试点 | 数据范围 | 说明 |
|---|---|---|
| 1~2 | 中仅包含 a 和 b 两种字符 |
无 |
| 3~4 | $1 \le | S |
| 全部 |