LeetCode 30: Substring with Concatenation of All Words (Offset Sliding Window)
LeetCode 30StringSliding WindowHash TableToday we solve LeetCode 30 - Substring with Concatenation of All Words.
Source: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
English
Problem Summary
Given a string s and an array words where each word has the same length, return all starting indices of substrings in s that are formed by concatenating every word exactly once (any order, no gaps).
Key Insight
All words share one fixed length wLen. So valid concatenations must align on one of wLen offsets. For each offset, process chunks of length wLen using a sliding window and a frequency map.
Brute Force and Limitations
Check every index and rebuild a full count map for the next k * wLen characters (k = words.length). This costs roughly O(n * k) word checks and repeated map construction.
Optimal Algorithm Steps
1) Build need[word] counts from words.
2) For each offset start in [0, wLen-1], run window pointers left, right stepping by wLen.
3) Read token s[right:right+wLen].
4) If token not needed: clear current map and reset window after token.
5) If needed: add token; while token count exceeds need, shrink from left by one token.
6) When window token count equals k, record left, then slide one token forward to keep searching.
Complexity Analysis
Time: O(n) token processing across all offsets (each token enters/leaves window at most once per offset).
Space: O(k) for frequency maps.
Common Pitfalls
- Forgetting to loop through all offsets 0..wLen-1.
- Not shrinking when a word count exceeds target frequency.
- Using character-step window instead of word-step window, causing misalignment bugs.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public java.util.List<Integer> findSubstring(String s, String[] words) {
java.util.List<Integer> ans = new java.util.ArrayList<>();
if (s == null || words == null || words.length == 0) return ans;
int wLen = words[0].length();
int k = words.length;
int totalLen = wLen * k;
if (s.length() < totalLen) return ans;
java.util.Map<String, Integer> need = new java.util.HashMap<>();
for (String w : words) need.put(w, need.getOrDefault(w, 0) + 1);
for (int offset = 0; offset < wLen; offset++) {
int left = offset, count = 0;
java.util.Map<String, Integer> win = new java.util.HashMap<>();
for (int right = offset; right + wLen <= s.length(); right += wLen) {
String word = s.substring(right, right + wLen);
if (!need.containsKey(word)) {
win.clear();
count = 0;
left = right + wLen;
continue;
}
win.put(word, win.getOrDefault(word, 0) + 1);
count++;
while (win.get(word) > need.get(word)) {
String drop = s.substring(left, left + wLen);
win.put(drop, win.get(drop) - 1);
left += wLen;
count--;
}
if (count == k) {
ans.add(left);
String drop = s.substring(left, left + wLen);
win.put(drop, win.get(drop) - 1);
left += wLen;
count--;
}
}
}
return ans;
}
}func findSubstring(s string, words []string) []int {
ans := []int{}
if len(words) == 0 {
return ans
}
wLen := len(words[0])
k := len(words)
totalLen := wLen * k
if len(s) < totalLen {
return ans
}
need := map[string]int{}
for _, w := range words {
need[w]++
}
for offset := 0; offset < wLen; offset++ {
left, count := offset, 0
win := map[string]int{}
for right := offset; right+wLen <= len(s); right += wLen {
word := s[right : right+wLen]
if _, ok := need[word]; !ok {
win = map[string]int{}
count = 0
left = right + wLen
continue
}
win[word]++
count++
for win[word] > need[word] {
drop := s[left : left+wLen]
win[drop]--
left += wLen
count--
}
if count == k {
ans = append(ans, left)
drop := s[left : left+wLen]
win[drop]--
left += wLen
count--
}
}
}
return ans
}class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if (words.empty()) return ans;
int wLen = words[0].size();
int k = words.size();
int totalLen = wLen * k;
if ((int)s.size() < totalLen) return ans;
unordered_map<string, int> need;
for (auto& w : words) need[w]++;
for (int offset = 0; offset < wLen; ++offset) {
int left = offset, count = 0;
unordered_map<string, int> win;
for (int right = offset; right + wLen <= (int)s.size(); right += wLen) {
string word = s.substr(right, wLen);
if (!need.count(word)) {
win.clear();
count = 0;
left = right + wLen;
continue;
}
win[word]++;
count++;
while (win[word] > need[word]) {
string drop = s.substr(left, wLen);
win[drop]--;
left += wLen;
count--;
}
if (count == k) {
ans.push_back(left);
string drop = s.substr(left, wLen);
win[drop]--;
left += wLen;
count--;
}
}
}
return ans;
}
};class Solution:
def findSubstring(self, s: str, words: list[str]) -> list[int]:
if not words:
return []
w_len = len(words[0])
k = len(words)
total_len = w_len * k
if len(s) < total_len:
return []
need: dict[str, int] = {}
for w in words:
need[w] = need.get(w, 0) + 1
ans: list[int] = []
for offset in range(w_len):
left = offset
count = 0
win: dict[str, int] = {}
for right in range(offset, len(s) - w_len + 1, w_len):
word = s[right:right + w_len]
if word not in need:
win.clear()
count = 0
left = right + w_len
continue
win[word] = win.get(word, 0) + 1
count += 1
while win[word] > need[word]:
drop = s[left:left + w_len]
win[drop] -= 1
left += w_len
count -= 1
if count == k:
ans.append(left)
drop = s[left:left + w_len]
win[drop] -= 1
left += w_len
count -= 1
return ansvar findSubstring = function(s, words) {
const ans = [];
if (!words || words.length === 0) return ans;
const wLen = words[0].length;
const k = words.length;
const totalLen = wLen * k;
if (s.length < totalLen) return ans;
const need = new Map();
for (const w of words) {
need.set(w, (need.get(w) || 0) + 1);
}
for (let offset = 0; offset < wLen; offset++) {
let left = offset;
let count = 0;
const win = new Map();
for (let right = offset; right + wLen <= s.length; right += wLen) {
const word = s.slice(right, right + wLen);
if (!need.has(word)) {
win.clear();
count = 0;
left = right + wLen;
continue;
}
win.set(word, (win.get(word) || 0) + 1);
count++;
while (win.get(word) > need.get(word)) {
const drop = s.slice(left, left + wLen);
win.set(drop, win.get(drop) - 1);
left += wLen;
count--;
}
if (count === k) {
ans.push(left);
const drop = s.slice(left, left + wLen);
win.set(drop, win.get(drop) - 1);
left += wLen;
count--;
}
}
}
return ans;
};中文
题目概述
给定字符串 s 和等长单词数组 words，找出所有起始下标，使得从该下标开始的子串恰好由 words 中全部单词拼接而成（每个单词使用一次，顺序可任意，且无多余字符）。
核心思路
因为每个单词长度固定为 wLen，合法拼接只能落在固定步长的分组上。我们按 0..wLen-1 不同偏移分别做滑动窗口，每次读一个“单词块”，用哈希表维护窗口词频。
暴力解法与不足
从每个下标出发，硬切 k 个单词并重建词频比较，重复工作很多，复杂度接近 O(n * k)，常数也大。
最优算法步骤
1）先统计目标词频 need。
2）对每个偏移 offset 建立窗口，左右指针按 wLen 跳。
3）读取当前块 word。
4）若不在 need 中，窗口清空并重置左边界。
5）若在 need 中，加入窗口；若该词超频，持续从左侧弹出直到合法。
6）当窗口块数等于 k 时记录答案，然后左移一个块继续找下一个起点。
复杂度分析
时间复杂度：O(n)（按块推进，每块最多进出窗口一次）。
空间复杂度：O(k)（目标词频 + 窗口词频）。
常见陷阱
- 漏掉不同偏移起点的扫描。
- 单词超频后没有及时收缩窗口。
- 用逐字符滑窗而不是逐单词滑窗，导致错位。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public java.util.List<Integer> findSubstring(String s, String[] words) {
java.util.List<Integer> ans = new java.util.ArrayList<>();
if (s == null || words == null || words.length == 0) return ans;
int wLen = words[0].length();
int k = words.length;
int totalLen = wLen * k;
if (s.length() < totalLen) return ans;
java.util.Map<String, Integer> need = new java.util.HashMap<>();
for (String w : words) need.put(w, need.getOrDefault(w, 0) + 1);
for (int offset = 0; offset < wLen; offset++) {
int left = offset, count = 0;
java.util.Map<String, Integer> win = new java.util.HashMap<>();
for (int right = offset; right + wLen <= s.length(); right += wLen) {
String word = s.substring(right, right + wLen);
if (!need.containsKey(word)) {
win.clear();
count = 0;
left = right + wLen;
continue;
}
win.put(word, win.getOrDefault(word, 0) + 1);
count++;
while (win.get(word) > need.get(word)) {
String drop = s.substring(left, left + wLen);
win.put(drop, win.get(drop) - 1);
left += wLen;
count--;
}
if (count == k) {
ans.add(left);
String drop = s.substring(left, left + wLen);
win.put(drop, win.get(drop) - 1);
left += wLen;
count--;
}
}
}
return ans;
}
}func findSubstring(s string, words []string) []int {
ans := []int{}
if len(words) == 0 {
return ans
}
wLen := len(words[0])
k := len(words)
totalLen := wLen * k
if len(s) < totalLen {
return ans
}
need := map[string]int{}
for _, w := range words {
need[w]++
}
for offset := 0; offset < wLen; offset++ {
left, count := offset, 0
win := map[string]int{}
for right := offset; right+wLen <= len(s); right += wLen {
word := s[right : right+wLen]
if _, ok := need[word]; !ok {
win = map[string]int{}
count = 0
left = right + wLen
continue
}
win[word]++
count++
for win[word] > need[word] {
drop := s[left : left+wLen]
win[drop]--
left += wLen
count--
}
if count == k {
ans = append(ans, left)
drop := s[left : left+wLen]
win[drop]--
left += wLen
count--
}
}
}
return ans
}class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if (words.empty()) return ans;
int wLen = words[0].size();
int k = words.size();
int totalLen = wLen * k;
if ((int)s.size() < totalLen) return ans;
unordered_map<string, int> need;
for (auto& w : words) need[w]++;
for (int offset = 0; offset < wLen; ++offset) {
int left = offset, count = 0;
unordered_map<string, int> win;
for (int right = offset; right + wLen <= (int)s.size(); right += wLen) {
string word = s.substr(right, wLen);
if (!need.count(word)) {
win.clear();
count = 0;
left = right + wLen;
continue;
}
win[word]++;
count++;
while (win[word] > need[word]) {
string drop = s.substr(left, wLen);
win[drop]--;
left += wLen;
count--;
}
if (count == k) {
ans.push_back(left);
string drop = s.substr(left, wLen);
win[drop]--;
left += wLen;
count--;
}
}
}
return ans;
}
};class Solution:
def findSubstring(self, s: str, words: list[str]) -> list[int]:
if not words:
return []
w_len = len(words[0])
k = len(words)
total_len = w_len * k
if len(s) < total_len:
return []
need: dict[str, int] = {}
for w in words:
need[w] = need.get(w, 0) + 1
ans: list[int] = []
for offset in range(w_len):
left = offset
count = 0
win: dict[str, int] = {}
for right in range(offset, len(s) - w_len + 1, w_len):
word = s[right:right + w_len]
if word not in need:
win.clear()
count = 0
left = right + w_len
continue
win[word] = win.get(word, 0) + 1
count += 1
while win[word] > need[word]:
drop = s[left:left + w_len]
win[drop] -= 1
left += w_len
count -= 1
if count == k:
ans.append(left)
drop = s[left:left + w_len]
win[drop] -= 1
left += w_len
count -= 1
return ansvar findSubstring = function(s, words) {
const ans = [];
if (!words || words.length === 0) return ans;
const wLen = words[0].length;
const k = words.length;
const totalLen = wLen * k;
if (s.length < totalLen) return ans;
const need = new Map();
for (const w of words) {
need.set(w, (need.get(w) || 0) + 1);
}
for (let offset = 0; offset < wLen; offset++) {
let left = offset;
let count = 0;
const win = new Map();
for (let right = offset; right + wLen <= s.length; right += wLen) {
const word = s.slice(right, right + wLen);
if (!need.has(word)) {
win.clear();
count = 0;
left = right + wLen;
continue;
}
win.set(word, (win.get(word) || 0) + 1);
count++;
while (win.get(word) > need.get(word)) {
const drop = s.slice(left, left + wLen);
win.set(drop, win.get(drop) - 1);
left += wLen;
count--;
}
if (count === k) {
ans.push(left);
const drop = s.slice(left, left + wLen);
win.set(drop, win.get(drop) - 1);
left += wLen;
count--;
}
}
}
return ans;
};
Comments