30

30. Substring with Concatenation of All Words (Hard)

You are given a string s and an array of strings words 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 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" 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: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

 

Constraints:

• 1 <= s.length <= 104
• s consists of lower-case English letters.
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] consists of lower-case English letters.

Companies:
Amazon, Apple

Related Topics:
Hash Table, String, Sliding Window

Similar Questions:

• Minimum Window Substring (Hard)

Solution 1. Fixed-length Sliding Window

// OJ: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
// Author: github.com/lzl124631x
// Time: O(MNL) where `M` is length of `A[i]`, `N` is length of `s`, and `L` is length of `A`.
// Space: O(ML)
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& A) {
        int N = s.size(), M = A[0].size(), len = M * A.size();
        unordered_map<string, int> cnt, tmp;
        for (auto &w : A) cnt[w]++;
        vector<int> ans;
        for (int start = 0; start < M; ++start) {
            tmp.clear();
            int matched = 0;
            for (int i = start; i < N; i += M) {
                auto w = s.substr(i, M);
                if (cnt.count(w) && ++tmp[w] <= cnt[w]) matched++;
                if (i - len >= 0) {
                    auto rm = s.substr(i - len, M);
                    if (cnt.count(rm) && --tmp[rm] < cnt[rm]) matched--;
                }
                if (matched == A.size()) ans.push_back(i - len + M);
            }
        }
        return ans;
    }
};

Solution 2. Backtracking

// OJ: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
// Author: github.com/lzl124631x
// Time: O(MNL)
// Space: O(ML)
class Solution {
private:
public:
    vector<int> findSubstring(string s, vector<string>& A) {
        if (A.empty()) return {};
        int L = A.size(), M = A[0].size(), last = s.size() - M * L;
        unordered_map<string, int> cnt;
        for (auto &w : A) ++cnt[w];
        vector<int> ans;
        function<bool(int, int)> dfs = [&](int i, int seen) {
            if (seen == L) return true;
            int &c = cnt[s.substr(i, M)];
            if (!c) return false;
            c--;
            bool ans = dfs(i + M, seen + 1);
            c++;
            return ans;
        };
        for (int i = 0; i <= last; ++i) {
            if (dfs(i, 0)) ans.push_back(i);
        }
        return ans;
    }
};