算法分析
对于幸福子串只需满足在区间中每个字符出现的次数都是偶数即可,因此,每个字符在区间左端开始的累加和的奇偶性在左右两端应该应该是一致的。每个字符的奇偶性可以用 1 bit
表示,所以可以用 int
表示
类似题: LC1371
Python 代码
from collections import Counter
ans, now = 0, 0
cnt = Counter()
cnt[now] += 1
for x in map(int, input()):
now ^= 1<<x
ans += cnt[now]
cnt[now] += 1
print(ans)