Sponsored
Sponsored
This approach uses a sliding window to find matching substrings. We utilize two hashmaps: one for the word list to track required counts of each word, and another to track what an occurring window currently constitutes.
The window slides over the string s while maintaining a fixed size (product of total words and word length). Each time the end of the window is extended, we evaluate if the slice of the string corresponds to a valid word by checking in the hashmap.
Time complexity: O(n * m * k) where n is the length of the string, m is the length of each word, and k is the number of words.
Space complexity: O(m) for the dictionaries holding word counts.
1import java.util.*;
2
3public List<Integer> findSubstring(String s, String[] words) {
4 if (words.length == 0) return Collections.emptyList();
5 Map<String, Integer> wordCount = new HashMap<>();
6 for (String word : words) wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
7
8 int wordLength = words[0].length();
9 int subStringLength = wordLength * words.length;
10 List<Integer> indices = new ArrayList<>();
11
12 for (int i = 0; i <= s.length() - subStringLength; i++) {
13 Map<String, Integer> seen = new HashMap<>();
14 int j = 0;
15 while (j < words.length) {
16 int wordIndex = i + j * wordLength;
17 String sub = s.substring(wordIndex, wordIndex + wordLength);
18 if (!wordCount.containsKey(sub)) break;
19 seen.put(sub, seen.getOrDefault(sub, 0) + 1);
20 if (seen.get(sub) > wordCount.get(sub)) break;
21 j++;
22 }
23 if (j == words.length) indices.add(i);
24 }
25 return indices;
26}The Java solution keeps maps as dictionary for word count and traverses using a similar sliding-window technique. Every window that matches the dictionary will satisfy permutation check.