# 30 Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:

```
s: "barfoothefoobarman"
words: ["foo", "bar"]
```

You should return the indices: \[0,9].\
(order does not matter).

**The Idea:** The following is a brute force procedure. First I conclude the size of the complete substring I should expect. Call is `cmpl_s`. Since all the words are the same length, and I know the amount - I can determine this. Then iterating through `s`, I take each `cmpl_s` and split it into equal size chunks. Finally, I confirm that all of these words exists within the word set uniquely. If so, the index `i` within the first level for loop gets recorded into the returning vector.

**Complexity:** O(N^2) time, O(N) space

```cpp
unordered_map<string, int> getWordFreq(const vector<string> &words) {
    unordered_map<string, int> word_freq;
    word_freq.reserve(words.size());

    for (const string &s : words) {
        if (word_freq.find(s) != word_freq.end())
            word_freq[s]++;
        else word_freq.insert({ s, 1 });
    }

    return word_freq;
}

vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> substringSeq;
    if (words.empty()) return substringSeq;

    const size_t word_length = words.at(0).length();
    unordered_map<string, int> word_freq = getWordFreq(words);
    unordered_map<string, int> word_freq_cp = word_freq;

    const int total_word_dist = words.size() * word_length;
    const int end = s.length() - total_word_dist + 1;

    for (int i = 0; i < end; i++) {
        string cmplt_words = s.substr(i, total_word_dist);

        for (int j = 0; j < total_word_dist; j += word_length) {
            string cur_word = cmplt_words.substr(j, word_length);
            if (word_freq_cp.find(cur_word) == word_freq_cp.end())
                break;
            else {
                word_freq_cp[cur_word]--;
                if (word_freq_cp[cur_word] == 0)
                    word_freq_cp.erase(cur_word);
            }
        }

        if (word_freq_cp.empty())
            substringSeq.push_back(i);

        word_freq_cp = word_freq;
    }

    return substringSeq;
}
```

**Testing**

```cpp
int main()
{
    //           .        .
    string s1 = "barfoothefoobarman";
    vector<string> words1 = {"foo", "bar" };
    print(findSubstring(s1, words1));

    //           .     .
    string s2 = "barfoobarfoo";
    vector<string> words2 = { "foo", "bar" };
    print(findSubstring(s2, words2));

    //           0123456789012345678901234567890123456789
    //                     .        .     .       .
    string s3 = "fooybarmanfoobarmanfoobarbarfoooofoobarr";
    vector<string> words3 = { "foo", "bar" };
    print(findSubstring(s3, words3));

    //           012345678901234567890123
    //                 .  .  .
    string s4 = "barfoofoobarthefoobarman";
    vector<string> words4 = { "foo", "bar", "the" };
    print(findSubstring(s4, words4));

    //           012345678901234567890123
    //                   .           
    string s5 = "wordgoodgoodgoodbestword";
    vector<string> words5 = { "word","good","best","good" };
    print(findSubstring(s5, words5));
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/30_substring_with_concatenation_of_all_words.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.