Problem
You are given a string s and an array of strings words, where all words have the same length.Return an array containing the starting indices of every substring in s that is formed by concatenating every word in words exactly once, in any order.
Example
Consider the following example to understand the expected input and output.Input
s = "barfoothefoobarman"
words = ["foo","bar"]Output
[0,9]Solution
This solution uses the Sliding Window technique along with a HashMap to track the frequency of words in the current window.Since every word has the same length, we can move through the string in steps of wordLen. For each starting position, we maintain a window containing complete words and track how many times each word appears.
The wordCount map stores the required frequency of every word. The windowCount map stores the frequency of words currently present in the sliding window. When a word is not present in wordCount, the current window is invalid, so we reset it.
If a word appears more times than required, we move the left side of the window forward by one word at a time until the frequency becomes valid again. When the window contains exactly words.length words, its starting index is added to the result.
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (s == null || words == null || words.length == 0) {
return result;
}
int wordLen = words[0].length();
int wordCount = words.length;
int totalLen = wordLen * wordCount;
if (s.length() < totalLen) {
return result;
}
Map<String, Integer> wordMap = new HashMap<>();
for (String word : words) {
wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
}
for (int offset = 0; offset < wordLen; offset++) {
int left = offset;
int count = 0;
Map<String, Integer> window = new HashMap<>();
for (int right = offset; right + wordLen <= s.length(); right += wordLen) {
String word = s.substring(right, right + wordLen);
// Invalid word: reset the current window.
if (!wordMap.containsKey(word)) {
window.clear();
count = 0;
left = right + wordLen;
continue;
}
window.put(word, window.getOrDefault(word, 0) + 1);
count++;
// Remove words while the current word appears too many times.
while (window.get(word) > wordMap.get(word)) {
String leftWord = s.substring(left, left + wordLen);
window.put(leftWord, window.get(leftWord) - 1);
left += wordLen;
count--;
}
// Current window contains all words exactly once.
if (count == wordCount) {
result.add(left);
String leftWord = s.substring(left, left + wordLen);
window.put(leftWord, window.get(leftWord) - 1);
left += wordLen;
count--;
}
}
}
return result;
}Complexity
The string is traversed using wordLen different offsets, and each word enters and leaves the sliding window at most once for each offset.Therefore, the overall time complexity is O(n) with respect to the length of s, assuming substring extraction and HashMap operations take constant time for the fixed word length.
The HashMap stores the required and current word frequencies, and the sliding window can contain at most words.length words. Therefore, the extra space complexity is O(m), where m is the number of words.
