题目描述

题目名称：可重排回文子串计数 II

给定一个仅包含小写英文字母的字符串 S 以及一个正整数 L，统计 S 中所有长度至少为 L 的子串中，有多少个可以通过重新排列后构成回文。
一个字符串可重排成回文的充要条件是：其中至多只有一个字符出现奇数次。

输入格式

• 第一行包含两个正整数 n 和 L，分别表示字符串 S 的长度和子串的最小长度要求。
• 第二行包含一个仅由小写字母组成的字符串 S（长度为 n）。

输出格式

• 输出一行，一个整数，表示满足条件的子串个数。

数据范围

• 1 ≤ n ≤ 200,000
• 1 ≤ L ≤ n

样例

输入：

9 3
abaabaaba

输出：

22

算法思路

1. 前缀状态构造
   定义前缀状态 P[i]（0 ≤ i ≤ n），其中 P[i] 用一个整数的二进制表示：

   • 第 j 位（0 ≤ j < 26）表示字母 ('a' + j) 在 S 的前 i 个字符中出现次数的奇偶性（1 表示奇数，0 表示偶数）。
     初始状态 P[0] = 0 表示空串。

2. 子串状态
   对于任意子串 S[i … j]（0 ≤ i ≤ j < n），其奇偶性状态为 P[j+1] XOR P[i]。
   当且仅当 popcount(P[j+1] XOR P[i]) ≤ 1 时，该子串可重排成回文。

3. 统计方法
   为了满足子串长度至少为 L，对于每个终点 j（ j 从 L-1 到 n-1 ），只有起点 i 满足 0 ≤ i ≤ j - L + 1 时构成的子串 S[i … j] 才有效。
   使用哈希表 freq 维护当前“滑动窗口”（即所有 i ∈ [0, j-L+1]）中前缀状态出现次数。
   对于当前终点 j，设 cur = P[j+1]，则：

   • 所有满足 P[i] = cur 的 i 对应的子串 S[i … j] 的状态为 0（popcount 0）。
   • 对于每个 0 ≤ b < 26，若存在 P[i] = cur XOR (1 << b) 的情况，则 S[i … j] 的状态只有一位 1。
     将这两种情况的频次累加，即为以 j 为终点且长度至少 L 的满足条件子串个数。

输出结果

对于样例输入：

9 3
abaabaaba

运行上述代码，将输出：

22