千问 LeetCode 2953. 统计完全子字符串 Java实现
这道题是一道经典的“分组循环 + 定长滑动窗口”问题。我们需要同时满足两个条件，直接暴力求解会非常复杂，因此核心思路是将两个条件拆分开来独立处理。
题目解析
一个子字符串是“完全”的，需要满足：
1. 字符频率条件：子字符串中每个出现的字符，都恰好出现 k 次。
2. 相邻字符条件：子字符串中任意两个相邻字符，在字母表中的顺序至多相差 2。
核心思路
1. 分组循环（处理相邻字符条件）：
由于条件2限制了相邻字符的差值，我们可以遍历整个字符串，每当遇到两个相邻字符的差值超过 2 时，就将字符串切分开。这样，原字符串就被分成了若干个独立的“块”，我们只需要在每个独立的块内部去统计满足条件1的子字符串即可。
2. 定长滑动窗口（处理字符频率条件）：
对于每一个独立的块，如果其中包含了 x 种不同的字符，那么满足条件1的子字符串长度一定是 x * k。
因为字符只有 26 个小写字母，所以我们可以枚举子字符串中包含的字符种类数 m（从 1 到 26）。对于每一个 m，窗口的固定长度就是 windowLen = m * k。我们使用滑动窗口在该块内滑动，检查窗口内的每个字符是否都恰好出现了 k 次。
Java 代码实现
class Solution {
public int countCompleteSubstrings(String word, int k) {
int n = word.length();
int totalRes = 0;
// 1. 分组循环：根据相邻字符差值 > 2 来切分字符串
for (int i = 0; i < n; ) {
int start = i;
i++;
// 只要相邻字符满足条件，就不断向后扩展当前组
while (i < n && Math.abs(word.charAt(i) - word.charAt(i - 1)) <= 2) {
i++;
}
// 对切分出来的子串 word[start, i) 单独计算满足条件1的子字符串数量
totalRes += countInSubstring(word.substring(start, i), k);
}
return totalRes;
}
// 2. 在独立的子串中，使用定长滑动窗口统计完全子字符串
private int countInSubstring(String s, int k) {
int len = s.length();
int res = 0;
// 枚举窗口内包含的字符种类数 m (1 到 26)
for (int m = 1; m <= 26 && m * k <= len; m++) {
int windowLen = m * k;
int[] freq = new int[26]; // 记录窗口内各字符的频率
// 滑动窗口遍历子串 s
for (int right = 0; right < len; right++) {
// 字符进入窗口
freq[s.charAt(right) - 'a']++;
// 计算当前窗口的左边界
int left = right + 1 - windowLen;
// 当窗口大小达到 windowLen 时开始判断
if (left >= 0) {
// 检查窗口内所有字符是否都恰好出现 k 次
boolean isValid = true;
for (int count : freq) {
// 如果某个字符出现过，但次数不等于 k，则不合法
if (count > 0 && count != k) {
isValid = false;
break;
}
}
if (isValid) {
res++;
}
// 字符滑出窗口，为下一次循环做准备
freq[s.charAt(left) - 'a']--;
}
}
}
return res;
}
}
复杂度分析
* 时间复杂度：O(26 * n)，即 O(n)。其中 n 是字符串 word 的长度。我们遍历字符串进行分组是 O(n)，在 countInSubstring 方法中，虽然有两层循环，但外层枚举字符种类最多 26 次，内层滑动窗口遍历子串，每个字符最多被访问常数次。
* 空间复杂度：O(1)。我们使用了一个固定大小为 26 的数组 freq 来记录字符频率，以及 substring 产生的临时空间（在 Java 新版本中 substring 会拷贝字符数组，但长度受限于 n，且通常视为常数级或 O(n) 的临时开销，整体空间复杂度非常低）。