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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

vector<int> findSubstring(string s, vector<string>& words) { // time: O(str_len * (# of words)); space: O(# of words)
    vector<int> res;
    if (s.empty() || words.empty()) return res;
    int n = words.size(), m = words[0].size();
    unordered_map<string, int> m1;
    for (const string& word : words) ++m1[word];
    for (int i = 0; i < s.length() - n * m; ++i) {
        unordered_map<string, int> m2;
        int j = 0;
        for (; j < n; ++j) {
            string t = s.substr(i + j * m, m);
            if (!m1.count(t)) break;
            ++m2[t];
            if (m2[t] > m1[t]) break;
        }
        if (j == n) res.push_back(i);
    }
    return res;
}

vector<int> findSubstring(string s, vector<string>& words) { // time: O(cnt + n); space: O(cnt)
    vector<int> res;
    if (s.empty() || words.empty()) return res;
    int n = s.size(), cnt = words.size(), len = words[0].size();
    unordered_map<string, int> m1;
    for (string& str : words) ++m1[str];
    for (int i = 0; i < len; ++i) {
        int left = i, count = 0;
        unordered_map<string, int> m2;
        for (int j = i; j <= n - len; j += len) {
            string t = s.substr(j, len);
            if (m1.count(t)) {
                ++m2[t];
                if (m2[t] <= m1[t])
                    ++count;
                else {
                    while (m2[t] > m1[t]) {
                        string t1 = s.substr(left, len);
                        --m2[t1];
                        if (m2[t1] < m1[t1]) --count;
                        left += len;
                    }
                }
                if (count == cnt) {
                    res.push_back(left);
                    --m2[s.substr(left, len)];
                    --count;
                    left += len;
                }
            } else {
                m2.clear();
                count = 0;
                left = j + len;
            }
        }
    }
    return res;
}