Link to Question

HARD

Substring with Concatenation of All Words

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

Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example

Input:

s = "barfoothefoobarman", words = ["foo","bar"]

Output:

[0,9]

Explanation:
Substrings starting at index 0 and 9 are "barfoo" and "foobar". The output order does not matter.

---

Constraints

• 1 ≤ s.length ≤ 10⁴
• 1 ≤ words.length ≤ 5000
• 1 ≤ words[i].length ≤ 30
• s and words[i] consist of lowercase English letters.

---

Solution: Hash Map

• Time Complexity: O(N _ M _ L), where N = |s|, M = |words|, L = |words[0]|.
• Space Complexity: O(M * L)

C++

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> expected;
        for(auto& c : words) expected[c]++;
        vector<int> ans;
        int n = s.size(), w = words.size(), sz = words.back().size();
        for (int i = 0; i <= n - w * sz; i++) {
            unordered_map<string, int> cur;
            for(int j = 0; j < w; j++)
                cur[s.substr(i + j*sz, sz)]++;
            if (cur == expected)
                ans.push_back(i);
        }
        return ans;
    }
};