简答题
偏难
#17722
等价消除 题目描述 小 A 有一个仅包含小写英文字母的字符串 S。 对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字…
等价消除
题目描述
小 A 有一个仅包含小写英文字母的字符串 S。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。
小 A 想知道 S有多少子串是可以被等价消除的。
一个字符串 S'是S 的子串,当且仅当删去 S的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。
输入格式
第一行,一个正整数|S| ,表示字符串S 的长度。
第二行,一个仅包含小写英文字母的字符串 S。
输出格式
一行,一个整数,表示答案。
输入样例 1
输出样例 1
输入样例 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 << c)
if state not in cnt:
cnt[state] = 0
ans += cnt[state]
cnt[state] += 1
print(ans)</pre>
这道题暂未补解析。