Substring With Concatenation of All Words

Problem

Given a string s and a list of equal-length words, find all starting indices where a substring is exactly a concatenation of every word in the list, each used once, in any order.

Input:  s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0, 9]

Python Solution

def find_substring(s, words):
    if not words:
        return []
    word_len = len(words[0])
    total_len = word_len * len(words)
    word_count = {}
    for w in words:
        word_count[w] = word_count.get(w, 0) + 1
    result = []
    for offset in range(word_len):
        left = offset
        count = 0
        seen = {}
        for right in range(offset, len(s) - word_len + 1, word_len):
            word = s[right:right + word_len]
            if word in word_count:
                seen[word] = seen.get(word, 0) + 1
                count += 1
                while seen[word] > word_count[word]:
                    left_word = s[left:left + word_len]
                    seen[left_word] -= 1
                    count -= 1
                    left += word_len
                if count == len(words):
                    result.append(left)
                    left_word = s[left:left + word_len]
                    seen[left_word] -= 1
                    count -= 1
                    left += word_len
            else:
                seen.clear()
                count = 0
                left = right + word_len
    return result

C++ Solution

vector<int> findSubstring(string s, vector<string>& words) {
    if (words.empty()) return {};
    int wordLen = words[0].size(), numWords = words.size();
    unordered_map<string, int> wordCount;
    for (auto& w : words) wordCount[w]++;
    vector<int> result;
    for (int offset = 0; offset < wordLen; offset++) {
        int left = offset, count = 0;
        unordered_map<string, int> seen;
        for (int right = offset; right + wordLen <= s.size(); right += wordLen) {
            string word = s.substr(right, wordLen);
            if (wordCount.count(word)) {
                seen[word]++;
                count++;
                while (seen[word] > wordCount[word]) {
                    string leftWord = s.substr(left, wordLen);
                    seen[leftWord]--;
                    count--;
                    left += wordLen;
                }
                if (count == numWords) {
                    result.push_back(left);
                    string leftWord = s.substr(left, wordLen);
                    seen[leftWord]--;
                    count--;
                    left += wordLen;
                }
            } else {
                seen.clear();
                count = 0;
                left = right + wordLen;
            }
        }
    }
    return result;
}

Java Solution

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (words.length == 0) return result;
        int wordLen = words[0].length(), numWords = words.length;
        Map<String, Integer> wordCount = new HashMap<>();
        for (String w : words) wordCount.merge(w, 1, Integer::sum);
        for (int offset = 0; offset < wordLen; offset++) {
            int left = offset, count = 0;
            Map<String, Integer> seen = new HashMap<>();
            for (int right = offset; right + wordLen <= s.length(); right += wordLen) {
                String word = s.substring(right, right + wordLen);
                if (wordCount.containsKey(word)) {
                    seen.merge(word, 1, Integer::sum);
                    count++;
                    while (seen.get(word) > wordCount.get(word)) {
                        String leftWord = s.substring(left, left + wordLen);
                        seen.merge(leftWord, -1, Integer::sum);
                        count--;
                        left += wordLen;
                    }
                    if (count == numWords) {
                        result.add(left);
                        String leftWord = s.substring(left, left + wordLen);
                        seen.merge(leftWord, -1, Integer::sum);
                        count--;
                        left += wordLen;
                    }
                } else {
                    seen.clear();
                    count = 0;
                    left = right + wordLen;
                }
            }
        }
        return result;
    }
}

Complexity

Time: O(n · L) — where n is the string length and L is word length, since the string is scanned word_len times, each in O(n/L) word-sized steps. Space: O(numWords · L) for the frequency maps.