A71709. 等价消除
编程题
基础
知识点
题目描述
小A有一个仅包含小写英文字母的字符串 S 。
对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。
小A想知道 S 有多少子串是可以被等价消除的。
一个字符串 S' 是 S 的子串，当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 S' 。
输入格式
第一行，一个正整数 |S| ，表示字符串 S 的长度。
第二行，一个仅包含小写英文字母的字符串 S 。
输出格式
一行，一个整数，表示答案。
输入输出样例
输入 #1
7 aaaaabb
输出 #1
9
输入 #2
9 babacabab
输出 #2
2
说明/提示
数据范围
对于 20\% 的测试点，保证 S 中仅包含 a 和 b 两种字符。
对于另外 20\% 的测试点，保证 1 \leq |S| \leq 2000 。
对于所有测试点，保证 1 \leq |S| \leq 2 \times 10^5 。