LeetCode 题解工作台
统计重新排列后包含另一个字符串的子字符串数目 II
给你两个字符串 word1 和 word2 。 如果一个字符串 x 重新排列后， word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。 请你返回 word1 中 合法 子字符串 的数目。 注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。 示…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 滑动窗口（状态滚动更新）
答案摘要
题目实际上是求在 中，有多少个子串包含了 中的所有字符。我们可以使用滑动窗口来处理。 首先，如果 的长度小于 的长度，那么 中不可能包含 的所有字符，直接返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。
请你返回 word1 中 合法 子字符串 的数目。
注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。
示例 1：
输入：word1 = "bcca", word2 = "abc"
输出：1
解释：
唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。
示例 2：
输入：word1 = "abcabc", word2 = "abc"
输出：10
解释：
除了长度为 1 和 2 的所有子字符串都是合法的。
示例 3：
输入：word1 = "abcabc", word2 = "aaabc"
输出：0
解释：
1 <= word1.length <= 1061 <= word2.length <= 104word1和word2都只包含小写英文字母。
解题思路
方法一：滑动窗口
题目实际上是求在 中，有多少个子串包含了 中的所有字符。我们可以使用滑动窗口来处理。
首先，如果 的长度小于 的长度，那么 中不可能包含 的所有字符，直接返回 。
接下来，我们用一个哈希表或长度为 的数组 来统计 中的字符出现的次数。然后，我们用 来记录还需要多少个字符才能满足条件，初始化为 的长度。
接着，我们用一个滑动窗口 来记录当前窗口中的字符出现的次数。我们用 来记录满足条件的子串的个数，用 来记录窗口的左边界。
遍历 中的每个字符，对于当前字符 ，我们将其加入到 中，如果 的值等于 ，那么说明当前窗口中已经包含了 中的所有字符之一，那么 减一。如果 等于 ，说明当前窗口中包含了 中的所有字符，我们需要缩小窗口的左边界，直到 大于 。具体地，如果 等于 ，那么说明当前窗口中包含了 中的所有字符之一，那么缩小窗口的左边界之后，就不满足条件了，所以 加一，同时 减一。然后，我们将 加一。此时窗口为 ，那么对于任意 ， 都是满足条件的子串，一共有 个，我们累加到答案中。
遍历完 中的所有字符之后，我们就得到了答案。
时间复杂度 ，其中 和 分别是 和 的长度。空间复杂度 ，其中 是字符集，这里是小写字母集合，所以空间复杂度是常数级别的。
class Solution:
def validSubstringCount(self, word1: str, word2: str) -> int:
if len(word1) < len(word2):
return 0
cnt = Counter(word2)
need = len(cnt)
ans = l = 0
win = Counter()
for c in word1:
win[c] += 1
if win[c] == cnt[c]:
need -= 1
while need == 0:
if win[word1[l]] == cnt[word1[l]]:
need += 1
win[word1[l]] -= 1
l += 1
ans += l
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for familiarity with sliding window problems and hash table usage.
- question_mark
Test if the candidate can handle large input sizes efficiently.
- question_mark
Check for understanding of how to maintain running state updates within the window.
常见陷阱
外企场景- error
Forgetting to update the hash map efficiently as the window slides.
- error
Not adjusting the window size correctly when shifting the pointers.
- error
Overcomplicating the frequency comparison step, leading to inefficiencies.
进阶变体
外企场景- arrow_right_alt
Handling different string lengths for word1 and word2, particularly when word2 is much larger.
- arrow_right_alt
Optimizing the space complexity by avoiding unnecessary data structures.
- arrow_right_alt
Considering edge cases, such as when no valid substrings exist or when word2 is much shorter than word1.