简答题 偏难
#17722

等价消除 题目描述 小 A 有一个仅包含小写英文字母的字符串 S。 对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字…

等价消除

题目描述

小 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≤|S|≤2000。

对于所有测试点,保证 1≤|S|≤2*105 。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n = int(input()) s = input() state, cnt, ans = 0, {}, 0 cnt[0] = 1 for i in range(n): c = ord(s[i]) - ord('a') state ^= (1 &lt;&lt; c) if state not in cnt: cnt[state] = 0 ans += cnt[state] cnt[state] += 1 print(ans)</pre>
这道题暂未补解析。