30. 串联所有单词的子串（Substring with Concatenation of All Words）
难度：困难 | 主题：滑动窗口、哈希表、字符串
题目
给定一个字符串 s 和一个字符串数组 words。words 中所有字符串长度相同。s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。返回所有串联子串在 s 中的起始索引。
示例：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
思路
先讲个故事：拼图找位置
你有一堆拼图碎片（words），每块大小一样（单词长度相同）。你要在一幅大拼图（s）里找到所有能放下这些碎片的位置。
因为碎片可以从任意位置开始放，所以你得尝试所有可能的起始偏移量。每个偏移量下，你用一个”取景框”（滑动窗口）在大拼图上滑动，检查框内碎片是否和你的碎片堆完全匹配。
引导式推导：分偏移滑动窗口
words 中所有单词长度相同（word_len），要找 s 中恰好由 words 所有单词各出现一次拼接成的子串。
核心洞察：把问题转化为「固定大小的块滑动窗口」。子串总长度为 len(words) * word_len，可以看成由 word_len 个字符为一组的块组成。
s = "barfoothefoobarman", words = ["foo","bar"]
word_len = 3, num_words = 2, total_len = 6
offset=0: 按 3 步长滑动
"bar" → 匹配 bar ✓
"foo" → 匹配 foo ✓
→ count=2 == len(need) → 记录 left=0
offset=1: 按 3 步长滑动
"arf" → 不在 need 中，重置
...
offset=2: 按 3 步长滑动
"rfo" → 不在 need 中，重置
...
graph TD subgraph 分偏移滑动窗口 A["offset=0<br/>检查 0,3,6,9... 位置"] B["offset=1<br/>检查 1,4,7,10... 位置"] C["offset=2<br/>检查 2,5,8,11... 位置"] end A --> D["对每个偏移做固定窗口滑动"] B --> D C --> D D --> E["窗口大小 = num_words * word_len"] E --> F["窗口内单词频率 == need 频率<br/>→ 匹配成功"]
为什么必须对每个偏移分别做？ 因为子串可以从任意字符位置开始，不只是 word_len 的倍数位置。
代码
from collections import Counter
def findSubstring(self, s, words):
if not words or not s:
return []
word_len = len(words[0]) # 每个单词的长度
num_words = len(words) # 单词总数
total_len = word_len * num_words # 子串总长度
n = len(s)
need = Counter(words) # 目标单词频率表
result = []
for offset in range(word_len): # 对每个起始偏移做滑动窗口
left = offset # 窗口左边界
window = Counter() # 当前窗口内单词频率表
count = 0 # 窗口内已满足的单词种类数
for right in range(offset, n - word_len + 1, word_len): # 按单词步长前进
word = s[right:right + word_len] # 截取当前单词
if word not in need: # 非法单词，整个窗口作废
window.clear()
count = 0
left = right + word_len
continue
window[word] += 1
if window[word] == need[word]:
count += 1 # 该单词频率刚好达标
# 保持窗口内的单词总数为 num_words
while right - left + word_len > total_len:
left_word = s[left:left + word_len]
if window[left_word] == need[left_word]:
count -= 1 # 移出后不再达标
window[left_word] -= 1
if window[left_word] == 0:
del window[left_word]
left += word_len
if count == len(need): # 所有单词种类频率都达标
result.append(left)
return result
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n * word_len) | 对每个偏移（共 word_len 个）做一次 O(n) 的滑动窗口 |
| 空间 | O(m * word_len) | 哈希表存单词，m 是不同单词数 |
实战考量
频率分析
出现在：滑动窗口困难题，考察对固定块大小窗口的理解，以及多偏移处理。约 10% 的高难度常会出这种”分偏移”变形。
延伸思考
Q：如果 words 里单词长度不同呢？
A：本题保证相同，不同则问题复杂度大增，需要回溯或 Trie。
Q：时间复杂度能优化吗？
A：基本就是 O(n * word_len)，因为必须检查每个偏移。
Q：如果 s 很长但 words 很少，有优化吗？
A：可以用 Trie 或 AC 自动机加速单词匹配。
Q：遇到不在 need 中的单词为什么要重置窗口？
A：这个单词不能属于任何合法子串，包含它的所有窗口都不可能匹配。
易错点
-
多偏移循环不能少
-
遇到非法单词要重置窗口
-
窗口大小按单词数控制，不是字符数
-
right - left + word_len > total_len的比较
生活类比
串联所有单词的子串 → 拼图找位置
你有一堆拼图碎片，要在大拼图里找到所有能完整放下这些碎片的位置。
碎片可以从任意位置开始放，所以你得一行一行、一列一列地试。
分偏移滑动窗口就是”扫描线”——不放过任何一个可能的起始点。
相关题目
| 题目 | 关系 |
|---|---|
| 438找到字符串中所有字母异位词 | 固定字符窗口 |
| 76最小覆盖子串 | 不定长窗口 |
→ 返回题单：LeetCode学习路线图 > 九、滑动窗口
速记卡（面试闪卡）
Q1：一句话讲清「30. 串联所有单词的子串（Substring with Concatenation of All Words）」到底是什么？
A：在字符串里找出所有能由 words 全部单词任意排列拼接而成的起始位置。
Q2：题目核心 —— 怎么理解？
A：像在大拼图里找能完整放下所有碎片的位置，碎片大小一样可从任意点起；英文 Substring with Concatenation of All Words，按 word_len 切块滑动。
Q3：思路拆解 —— 怎么理解？
A：如同扫描线：因起点任意，需对每个偏移 offset 各做一次固定窗口滑动；英文 sliding window 滑动窗口，窗口大小 = 词数×词长。
Q4：代码骨架 —— 怎么理解？
A：好比查词典：用 Counter 记目标词频，窗口按词步走，遇非法词整窗作废，超长就从左边吐词；匹配则记 left。
Q5：复杂度与实战 —— 怎么理解？
A：如同对每个偏移都扫一遍，时间 O(n×word_len)、空间 O(m×word_len)；英文 sliding window 困难题，十道里约一道考”分偏移”。
Q6：核心速记主线有哪些？
-
分偏移：从 0 到 word_len-1 各扫一遍，起点任意
-
固定块：窗口 = 词数×词长，按词步长滑动
-
计数：Counter 比词频，非法词整窗重置
-
复杂度：时间 O(n×词长)，空间 O(不同词数×词长)
口诀
A：串联单词子串题
分偏移扫不漏点
固定窗口比词频
时间O(n乘词长)记