You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.


	For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.


Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

&nbsp;
Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.


Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.


Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 104
	1 &lt;= words.length &lt;= 5000
	1 &lt;= words[i].length &lt;= 30
	s and words[i] consist of lowercase English letters.


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        req={}
        for i in words:
            req[i]=1+req.get(i,0)
        l=0
        r=len(words)*len(words[0])
        ans=[]

        while r<len(s)+1:
            i=0
            curr={}
            left, right= l, l+len(words[0])
            while right<l+len(words)*len(words[0])+1:
                x=s[left:right]
                # print(x)
                if x in req.keys():
                    curr[x]= 1+ curr.get(x,0)
                left=right
                right=right+len(words[0])
            if req==curr:
                ans.append(l)
            l=l+1
            r=r+1
        return ans
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {

        HashMap<String, Integer> input = new HashMap<>();
        int ID = 1;
        HashMap<Integer, Integer> count = new HashMap<>();
        for(String word: words) {
            if(!input.containsKey(word))
                input.put(word, ID++);
            int id = input.get(word);
            count.put(id,count.getOrDefault(id,0)+1);

        }
        int len = s.length();
        int wordLen = words[0].length();
        int numWords = words.length;
        int windowLen = wordLen*numWords;
        int lastIndex = s.length()-windowLen;

        int curWordId[] = new int[len];
        String cur = " "+s.substring(0,wordLen-1);

        //Change to int array
        for(int i = 0; i< (len-wordLen+1); i++) {
            cur = cur.substring(1, cur.length())+s.charAt(i+wordLen-1);
            if(input.containsKey(cur)){
                curWordId[i] = input.get(cur);
            } else {
                curWordId[i] = -1;
            }
        }
        List<Integer> res = new ArrayList<>();

        //compare using int make it faster 30 times in each comparison
        for(int i = 0; i<= lastIndex; i++) {

            HashMap<Integer, Integer> winMap = new HashMap<>();
            for(int j = 0; j < windowLen && curWordId[i] != -1; j+=wordLen) {

                int candidate = curWordId[j+i];

                if(!count.containsKey(candidate))
                    break;
                else{
                    winMap.put(candidate, winMap.getOrDefault(candidate, 0)+1);
                }
                if(winMap.get(candidate) > count.get(candidate))
                    break;

                if(j == (windowLen - wordLen) && winMap.size() == count.size()){
                    res.add(i);

                }

            }
        }

        return res;
    }
}
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n = words[0].length();
        int slen = s.length();
        int len = slen - n*words.size();
        vector<int> ans;
        if( len < 0) return ans;
        string t;
        unordered_map<string, int> mp;
        for(auto i = 0; i < words.size(); ++i) ++mp[words[i]];

        for(int i = 0; i<= len; ++i){
            t = s.substr(i, n);
            if(mp.find(t) != mp.end()){
                unordered_map<string, int> smp;
                ++smp[t];
                int flag = 1;
                for(int j = i+n, k = 1; k < words.size() && j+n <= slen; ++k, j = j + n){
                    t = s.substr(j, n);
                    if(mp.find(t) != mp.end()) ++smp[t];
                    else {
                        flag = 0;
                        break;
                    }
                }
                if(flag && smp == mp) ans.push_back(i);
            }
        }

        return ans;
    }
};
var findSubstring = function(s, words) {
    
    let res = [];

    let wordLength = words[0].length;
    let wordCount = words.length;
    let len = wordCount * wordLength; //Length of sliding window
    
    let map = {}
    
    for (let word of words) map[word] = map[word] + 1 || 1; //Hash word freq

  	for (let i = 0; i < s.length - len + 1; i++) {
            let sub = s.slice(i, i + len); //Generate substring of sliding window length
            if (isConcat(sub, map, wordLength)) res.push(i)
        }
    
    return res;
};

function isConcat(sub,map,wordLength){
    
    let seen = {};
    for (let i = 0; i < sub.length; i+=wordLength) {
        let word = sub.slice(i,i + wordLength);
        seen[word] = seen[word] + 1 || 1
    }
    
    for(let key in map){
        if(map[key] !== seen[key]) return false; //Word freq must match between map and seen
    }
    return true;
}```
Substring with Concatenation of All Words