LeetCode 题解工作台
统计完全子字符串
给你一个字符串 word 和一个整数 k 。 如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串： s 中每个字符 恰好 出现 k 次。 相邻字符在字母表中的顺序 至多 相差 2 。也就是说， s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差 至多 为 2 。 请…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 滑动窗口（状态滚动更新）
答案摘要
根据题目描述中的条件 ，我们可以发现，一个完全字符串中，相邻两个字符之差不超过 。因此，我们遍历字符串 ，可以利用双指针把 分割成若干个子字符串，这些子字符串中的字符种类数不超过 ，且相邻字符之差不超过 。接下来，我们只需要在每个子字符串中，统计每个字符都出现 次的子字符串的个数即可。 我们定义一个函数 ，它的功能是统计字符串 中每个字符都出现 次的子字符串的个数。由于 中的字符种类数不…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个字符串 word 和一个整数 k 。
如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：
s中每个字符 恰好 出现k次。- 相邻字符在字母表中的顺序 至多 相差
2。也就是说，s中两个相邻字符c1和c2，它们在字母表中的位置相差 至多 为2。
请你返回 word 中 完全 子字符串的数目。
子字符串 指的是一个字符串中一段连续 非空 的字符序列。
示例 1：
输入：word = "igigee", k = 2 输出：3 解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。
示例 2：
输入：word = "aaabbbccc", k = 3 输出：6 解释：完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。
提示：
1 <= word.length <= 105word只包含小写英文字母。1 <= k <= word.length
解题思路
方法一：枚举字符种类数 + 滑动窗口
根据题目描述中的条件 ，我们可以发现，一个完全字符串中，相邻两个字符之差不超过 。因此，我们遍历字符串 ，可以利用双指针把 分割成若干个子字符串，这些子字符串中的字符种类数不超过 ，且相邻字符之差不超过 。接下来，我们只需要在每个子字符串中，统计每个字符都出现 次的子字符串的个数即可。
我们定义一个函数 ，它的功能是统计字符串 中每个字符都出现 次的子字符串的个数。由于 中的字符种类数不超过 ，因此我们可以枚举每个字符种类数 ，其中 ，那么每个字符种类数为 的子字符串的长度为 。
我们可以用一个数组或哈希表 维护一个长度为 的滑动窗口中每个字符出现的次数，用另一个哈希表 维护每个次数出现的次数。如果 ，即有 个字符都出现了 次，那么我们就找到了一个满足条件的子字符串。我们可以用双指针维护这个滑动窗口，每次移动右指针时，我们将右指针指向的字符出现的次数加一，并更新 数组；每次移动左指针时，我们将左指针指向的字符出现的次数减一，并更新 数组。在每次移动指针后，我们都判断 是否等于 ，如果等于则说明我们找到了一个满足条件的子字符串。
时间复杂度 ，空间复杂度 ，其中 是字符串 的长度；而 是字符集的大小，本题中字符集为小写英文字母，因此 。
class Solution:
def countCompleteSubstrings(self, word: str, k: int) -> int:
def f(s: str) -> int:
m = len(s)
ans = 0
for i in range(1, 27):
l = i * k
if l > m:
break
cnt = Counter(s[:l])
freq = Counter(cnt.values())
ans += freq[k] == i
for j in range(l, m):
freq[cnt[s[j]]] -= 1
cnt[s[j]] += 1
freq[cnt[s[j]]] += 1
freq[cnt[s[j - l]]] -= 1
cnt[s[j - l]] -= 1
freq[cnt[s[j - l]]] += 1
ans += freq[k] == i
return ans
n = len(word)
ans = i = 0
while i < n:
j = i + 1
while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2:
j += 1
ans += f(word[i:j])
i = j
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for understanding of sliding window techniques and how they can be adapted to maintain state in a problem like this.
- question_mark
Check the candidate's ability to use hash tables efficiently, especially in terms of managing dynamic frequencies within a sliding window.
- question_mark
Evaluate the candidate’s approach to validating substring constraints, specifically handling the adjacency condition and frequency checks simultaneously.
常见陷阱
外企场景- error
Failing to efficiently manage the sliding window or hash table, leading to excessive time complexity.
- error
Incorrectly handling edge cases where there are no valid complete substrings or when k is very large relative to the word length.
- error
Overcomplicating the problem by attempting unnecessary optimizations or brute force methods instead of leveraging efficient window management.
进阶变体
外企场景- arrow_right_alt
Increasing k or the length of the word, requiring more sophisticated state management in the sliding window.
- arrow_right_alt
Handling multiple overlapping valid substrings and ensuring they are counted correctly without duplication.
- arrow_right_alt
Modifying the condition for adjacency or frequency, e.g., allowing for a larger difference between characters or a range of allowed frequencies.