What is the main algorithmic technique for this problem?

The problem is best solved using a sliding window with dynamic hash table updates to track word frequencies as the window slides through the string.

How do you handle the frequency of words in the sliding window?

Use a hash table to track the count of each word in the current window. As the window slides, update the table by adding the new word and removing the old one.

Why is the sliding window approach efficient here?

The sliding window approach allows you to check potential substrings in a dynamic, incremental manner, avoiding the need to check every substring from scratch.

How do you handle cases where there is no valid concatenation?

If no valid concatenation is found during the sliding window process, simply return an empty array to indicate no matching substrings exist.

What is the space complexity of the algorithm?

The space complexity is O(m * k), where m is the length of each word, and k is the number of words, due to the hash table storing word frequencies.

#30

Hard

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words 。 words 中所有字符串长度相同。 s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。例如，如果 words = ["ab","cd","ef"] ，那么 "abcdef" ， "abefcd" ， …

哈希表字符串滑动窗口

题目描述

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

1 <= s.length <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

lightbulb

解题思路

方法一：哈希表 + 滑动窗口

我们用哈希表 $cnt$ 统计 $words$ 中每个单词出现的次数，用哈希表 $cnt1$ 统计当前滑动窗口中每个单词出现的次数。我们记字符串 $s$ 的长度为 $m$ ，字符串数组 $words$ 中单词的数量为 $n$ ，每个单词的长度为 $k$ 。

我们可以枚举滑动窗口的起点 $i$ ，其中 $0 \lt i \lt k$ 。对于每个起点，我们维护一个滑动窗口，左边界为 $l$ ，右边界为 $r$ ，滑动窗口中的单词个数为 $t$ ，另外用一个哈希表 $cnt1$ 统计滑动窗口中每个单词出现的次数。

每一次，我们提取字符串 $s[r:r+k]$ ，如果 $s[r:r+k]$ 不在哈希表 $cnt$ 中，说明当前滑动窗口中的单词不合法，我们将左边界 $l$ 更新为 $r$ ，同时将哈希表 $cnt1$ 清空，单词个数 $t$ 重置为 0。如果 $s[r:r+k]$ 在哈希表 $cnt$ 中，说明当前滑动窗口中的单词合法，我们将单词个数 $t$ 加 1，将哈希表 $cnt1$ 中 $s[r:r+k]$ 的次数加 1。如果 $cnt1[s[r:r+k]]$ 大于 $cnt[s[r:r+k]]$ ，说明当前滑动窗口中 $s[r:r+k]$ 出现的次数过多，我们需要将左边界 $l$ 右移，直到 $cnt1[s[r:r+k]] = cnt[s[r:r+k]]$ 。如果 $t = n$ ，说明当前滑动窗口中的单词正好合法，我们将左边界 $l$ 加入答案数组。

时间复杂度 $O(m \times k)$ ，空间复杂度 $O(n \times k)$ 。其中 $m$ 和 $n$ 分别是字符串 $s$ 和字符串数组 $words$ 的长度，而 $k$ 是字符串数组 $words$ 中单词的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        cnt = Counter(words)
        m, n = len(s), len(words)
        k = len(words[0])
        ans = []
        for i in range(k):
            l = r = i
            cnt1 = Counter()
            while r + k <= m:
                t = s[r : r + k]
                r += k
                if cnt[t] == 0:
                    l = r
                    cnt1.clear()
                    continue
                cnt1[t] += 1
                while cnt1[t] > cnt[t]:
                    rem = s[l : l + k]
                    l += k
                    cnt1[rem] -= 1
                if r - l == n * k:
                    ans.append(l)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to handle sliding window operations efficiently in this problem?
question_mark
Can you implement a hash table that dynamically updates word frequencies during the sliding window process?
question_mark
Will you be able to adjust the window size based on word count frequency in real-time?

warning

常见陷阱

外企场景

error
Failing to update the hash table correctly when sliding the window, leading to incorrect word counts.
error
Overlooking edge cases where words may not fully match the substring even if their individual counts are correct.
error
Not optimizing the window movement, leading to unnecessary comparisons that degrade performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Substring with Concatenation of All Words: Handle edge cases with non-overlapping words.
arrow_right_alt
Substring with Concatenation of All Words: Modify the problem to allow overlapping words.
arrow_right_alt
Substring with Concatenation of All Words: Extend to support words of different lengths.

help

常见问题

外企场景

继续练习

#3 无重复字符的最长子串 #76 最小覆盖子串 #187 重复的DNA序列