Back to DSA
Substring with Concatenation of All Words
hardA string and an array of equal-length words are given. Find every starting position in the string where a contiguous segment exactly matches some concatenation (in any order) of all the provided words. Each word must appear exactly as many times in the segment as it appears in the word list.
Examples
Example 1:
Input:
s = "catdogcatdog", words = ["cat","dog"]Output:
[0,3,6]Explanation: At index 0: 'catdog' is a valid concatenation. At index 3: 'dogcat' is valid. At index 6: 'catdog' is valid.
Example 2:
Input:
s = "abcdef", words = ["ab","cd","ef"]Output:
[0]Explanation: Only at index 0 does the substring 'abcdef' equal a valid concatenation of all three words.
Hints
import java.util.*;
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words.length == 0) return result;
int wordLen = words[0].length(), totalLen = wordLen * words.length;
Map<String, Integer> wordCount = new HashMap<>();
for (String w : words) wordCount.merge(w, 1, Integer::sum);
for (int i = 0; i <= s.length() - totalLen; i++) {
Map<String, Integer> seen = new HashMap<>();
int j = 0;
while (j < words.length) {
String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
seen.merge(word, 1, Integer::sum);
if (seen.get(word) > wordCount.getOrDefault(word, 0)) break;
j++;
}
if (j == words.length) result.add(i);
}
return result;
}
}Time complexity
O(n * w)Space complexity
O(m)