LeetCode 题解工作台
统计重新排列后包含另一个字符串的子字符串数目 I
给你两个字符串 word1 和 word2 。 如果一个字符串 x 重新排列后， word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。 请你返回 word1 中 合法 子字符串 的数目。 示例 1： 输入： word1 = "bcca", word2 = "abc" 输出： 1 …
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 <= 1051 <= 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 understanding of sliding window technique.
- question_mark
Evaluate the candidate's ability to optimize space and time complexity.
- question_mark
Test if the candidate can handle edge cases where word1 is smaller than word2 or has mismatched character frequencies.
常见陷阱
外企场景- error
Not properly updating the frequency count as the window slides.
- error
Forgetting to handle cases where word2 is longer than word1.
- error
Incorrectly comparing the frequency tables, which might lead to false positives for valid substrings.
进阶变体
外企场景- arrow_right_alt
What if word2 is empty? How would you handle that?
- arrow_right_alt
How can you modify the approach if word1 and word2 can contain uppercase letters?
- arrow_right_alt
How would the solution change if there were constraints on the number of distinct characters in word1?