← 返回题目
题库练习 等价消除
← 上一题 下一题 →

A71709 | 等价消除

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

小A有一个仅包含小写英文字母的字符串 S 。

对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。

小A想知道 S 有多少子串是可以被等价消除的。

一个字符串 S' 是 S 的子串，当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 S' 。

输入格式

第一行，一个正整数 |S| ，表示字符串 S 的长度。

第二行，一个仅包含小写英文字母的字符串 S 。

输出格式

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

输入输出样例

输入 #1
7
aaaaabb
输出 #1
9
输入 #2
9
babacabab
输出 #2
2
C++ 编辑器
输入
输出