Approach
All words have the same nonzero length, so we can scan aligned word-sized chunks with sliding windows. Process each starting offset from 0 through wordLength - 1. The target map stores the required frequency of each word, while window stores its frequency in the current window; this handles duplicate words as well as unique ones.
When the right side encounters a word absent from target, no valid concatenation can cross it: clear the window and move the left pointer to the position after that word. Otherwise, add the word and shrink from the left while its frequency exceeds the target frequency. When the window contains exactly words.length words, record its starting index, then remove its leftmost word. Shrinking once after a match preserves the possibility of finding overlapping matches. Since offsets are scanned separately, sort the collected indices before returning them.
Let N be the length of s, L the common word length, W the number of words, U the number of distinct words, and R the number of returned indices. Across all offsets, the right pointer processes O(N) word chunks. Extracting each chunk costs O(L), and sorting the results costs O(R log R), for a total time of O(N * L + R log R). The frequency maps and active window use O(U + W) space; the returned output uses an additional O(R).
Java
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words.length == 0) {
return result;
}
int wordLength = words[0].length();
int wordCount = words.length;
int totalLength = wordLength * wordCount;
if (s.length() < totalLength) {
return result;
}
Map<String, Integer> target = new HashMap<>();
for (String word : words) {
target.put(word, target.getOrDefault(word, 0) + 1);
}
for (int offset = 0; offset < wordLength; offset++) {
Map<String, Integer> window = new HashMap<>();
int left = offset;
int right = offset;
int count = 0;
while (right + wordLength <= s.length()) {
String word = s.substring(right, right + wordLength);
right += wordLength;
if (!target.containsKey(word)) {
window.clear();
count = 0;
left = right;
continue;
}
window.put(word, window.getOrDefault(word, 0) + 1);
count++;
while (window.get(word) > target.get(word)) {
String removed = s.substring(left, left + wordLength);
window.put(removed, window.get(removed) - 1);
left += wordLength;
count--;
}
if (count == wordCount) {
result.add(left);
String removed = s.substring(left, left + wordLength);
window.put(removed, window.get(removed) - 1);
left += wordLength;
count--;
}
}
}
Collections.sort(result);
return result;
}
}