等价消除

题目描述

⼩ A 有⼀个仅包含⼩写英⽂字母的字符串 。 对于⼀个字符串，如果能通过每次删去其中两个相同字符的⽅式，将这个字符串变为空串，那么称这个字符串是可 以被等价消除的。 ⼩ A 想知道 有多少⼦串是可以被等价消除的。 ⼀个字符串 是 的⼦串，当且仅当删去 的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 。

输入格式

第⼀⾏，⼀个正整数 ，表⽰字符串 的长度。 第⼆⾏，⼀个仅包含⼩写英⽂字母的字符串 。

输出格式

⼀⾏，⼀个整数，表⽰答案。

样例输入 #1

7
aaaaabb

样例输出 #1

9

样例输入 #2

9
babacabab

样例输出 #2

2

数据范围

对于 % 的测试点，保证 中仅包含 a 和 b 两种字符。 对于另外 % 的测试点，保证 。 对于所有测试点，保证 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。