思路:滑动窗口

使用一个哈希表bk来存储滑动窗口内的字母以及其对应出现次数。然后实现一个check函数来检查是否bk内存储的值全是偶数。

从左到右进行滑动窗口。从第k个字符开始，每次加上一个字符，减去一个字符。然后检查是否全是偶数

python

def check (): # 检查是否全是偶数
    for x in bk:
        if bk[x] % 2 != 0:

题目描述

小欧拿到了一个字符串，她想知道，有多少个长度为 $k$ 的连续子串满足，所有字母出现次数为偶数次，小红想知道，有多少个满足条件的子串 ?

输入描述

第一行输入两个正整数 $n$ 和 $k$，代表字符串长度和选择的子串长度

第二行输入一个长度为 $n$ 的 ，仅由小写字母组成的字符串， $1$ < $k$ < $n$ < $200000$。

输出描述

一个整数，代表满足条件的子串数量。

示例1

输入

5 2
aabbc

输出

2

示例2

输入

5 2
aaaaa