You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. Example : S: "barfoothefoobarman" L: ["foo", "bar"] You should return the indices: [0,9]. (order does not matter).

InterviewBit : Substring Concatenation

vector<int> Solution::findSubstring(string A, const vector<string> &B) {
    
    // For the result.
    vector<int> res;
    
    // Calculating the no of sub-component available.
    int sz = B.size();
    //cout << "totalComp" << " " << sz << endl;
    
    // Calculating the length of a single sub-compo. All have same length.
    int sz1 = B[0].size();
    
    // Calculating supposed len of total window.
    int szOfLi = sz*sz1;
    //cout << "totalComp" << " " << szOfLi << endl;
    
    // If total window len exceed string len. There is not hope to find any substring.
    if(szOfLi>A.size()){
        return res;
    }
    
    // Creating map to store the count of all the sub compo.
    map<string,int> m;
    
    
    for(int i=0;i<B.size();i++){
        m[B[i]]++;
    }
    
    
    // Sliding the window of check one by one.
    for(int i=0;i<A.size()-szOfLi+1;i++){
        
        // Creating a copy of the map. We need new copy every time.
        //cout << i << endl;
        map<string,int> cp;
        cp.insert(m.begin(),m.end());
        
        // If we find substring component. We will reduce it.
        for(int j=i ;j< i+szOfLi ; j=j+sz1){
            //cout << A.substr(j,sz1) << endl;
            cp[A.substr(j,sz1)]--;
        }
        
        // I will consider by default every window is eligible for entry.
        // But i will than check the condition.
        bool add = true;
        
        // I will iterate over the map and expect entries to be zero.
        for(auto it=cp.begin();it!=cp.end();it++){
            // If some entry is not zero. That's an issue.
            if(it->second!=0){
                add = false;
                break;
            }
        }
        
        // I will add the index.
        if(add){
            res.push_back(i);
        }
        
    }
    
    return res;
}