The problem requires searching a given string to find all the starting indices of the substrings that are a perfect concatenation of the list of the given words. Each word in the list of words must appear once and without any intervening characters.

Problem Explanation

Take, for instance, a given string s = "barfoothefoobarman" and a list of words words = ["foo","bar"]. The expected return would be [0,9].

The reason for this is; starting from index 0, the concatenation of the words in the list gives "barfoo", and starting from index 9, the concatenation gives "foobar". These two instances serve as the substrings in 's' which are perfect concatenations of words in the list 'words'.

However, if s = "wordgoodgoodgoodbestword" and words = ["word","good","best","word"], the return would be []. This is because no perfect concatenation of the words in 'words' exists in 's'.

Solution Approach

The proposed solution uses a sliding window approach and hash maps. First, a hash map is constructed with each word from 'words' and the frequency of each occurrence. Then we slide through string 's', creating substrings of size equal to the product of the size of 'words' and length of a word from 'words'. For each substring, another hash map is created with each constituent word and its frequency. If the hash map from this substring matches the original words hash map, the starting index of the substring is appended to the answer list.

Python Solution:

1
2python
3class Solution:
4    def findSubstring(self, s: str, words: List[str]) -> List[int]:
5        if not s or not words: 
6            return []
7        
8        wordBag = collections.Counter(words)
9        wordLen, numWords = len(words[0]), len(words)
10        totalLen, res = wordLen * numWords, []
11        
12        for i in range(len(s) - totalLen + 1):
13            seenWords = collections.Counter([s[j:j+wordLen] for j in range(i, i+totalLen, wordLen)]) 
14            if seenWords == wordBag: 
15                res.append(i)
16        
17        return res

Java Solution:

1
2java
3public class Solution {
4    public List<Integer> findSubstring(String s, String[] words) {
5        List<Integer> result = new ArrayList<>();
6        if(s == null || words == null || words.length == 0){
7            return result;
8        }
9        
10        int len = words[0].length();
11        Map<String, Integer> map = new HashMap<>();
12        for(String w : words){
13            map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1);
14        }
15        
16        for(int i=0;i<=s.length()-len*words.length;i++){
17            Map<String, Integer> copy = new HashMap<>(map);
18            for(int j=0;j<words.length;j++){
19                String str = s.substring(i+j*len, i+j*len+len);
20                if(copy.containsKey(str)){
21                    int count = copy.get(str);
22                    if(count == 1){
23                        copy.remove(str);
24                    }
25                    else{
26                        copy.put(str,count-1);
27                    }
28                    if(copy.isEmpty()){
29                        result.add(i);
30                        break;
31                    }
32                }
33                else{
34                    break;
35                }
36            }
37        }
38        
39        return result;
40    }
41}

JavaScript Solution:

1
2javascript
3var findSubstring = function(s, words) {
4    if (!words.length) return [];
5    
6    let ans = [],
7        hash = {},
8        counter = {},
9        wordNum = words.length,
10        wordLen = words[0].length,
11        sLen = s.length;
12    
13    for (let i=0; i<wordNum; i++) {
14        if (hash[words[i]]) hash[words[i]]++;
15        else hash[words[i]] = 1;
16    }
17    
18    for (let i=0; i<wordLen; i++) {
19        let l = i,
20            r = i,
21            count = 0;
22        
23        while(r+wordLen <= sLen) {
24            let w1 = s.substring(r,r+wordLen);
25            
26            counter[w1] = (counter[w1] || 0)+ 1;
27            r += wordLen;
28            count++;
29            
30            while(counter[w1] > hash[w1]) {
31                let w2 = s.substring(l,l+wordLen);
32                counter[w2] -= 1;
33                count--;
34                l += wordLen;
35            }
36            
37            if(count === wordNum) ans.push(l);
38        }
39        
40        counter = {};
41    }
42    
43    return ans;
44};

In all three solutions, note that the 'if not words or not s' check is required to handle edge cases where the string 's' or 'words' is empty.All three versions operate based on the sliding window notion. The algorithm first creates a hash map or counter with each distinct word in the 'words' array mapped to its frequency or count. Then, it creates a window of size equal to the total characters in all words in 'words'.

The algorithm glides this window over the string 's'. At each window, it determines a counter of the count of every word in the window. If the window’s counter equals the original counter from 'words', this indicates a perfect concatenation of the words in 'words', and so the starting index of the window substrings gets appended into the results list.

In Python, the 'collections' library's 'Counter' method proves handy in creating the necessary counters.

The Java implementation uses a 'HashMap' to serve the same purpose. When inspecting subsets of the string 's', a copy of the 'map' object gets created with the 'HashMap' copy constructor to allow modification of copy without editing the original 'map'.

JavaScript uses an object 'hash' to act as a counter. Going through the string 's', a temporary counter object gets created for each window.

The lines 'if not words or not s' in Python, 'if(s == null || words == null || words.length == 0)' in Java, and 'if (!words.length) return [];' in JavaScript serve to handle edge cases where the string 's', 'words' array is null or has no elements. The function returns an empty list or array if either 's' or 'words' don't have any elements since no concatentation would be possible.

In conclusion, the solution cleverly uses hash maps and a sliding window approach to solve the problem systematically and efficiently in all the three languages; Python, Java, JavaScript.