Substring with Concatenation of All Words

Problem Description

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.

Examples

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]

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def findSubstring(s: str, words: List[str]) -> List[int]:
    if not s or not words:
        return []
    
    word_len = len(words[0])
    word_count = len(words)
    total_len = word_len * word_count
    word_freq = Counter(words)
    result = []
    
    for i in range(len(s) - total_len + 1):
        seen = Counter()
        j = 0
        
        while j < word_count:
            word = s[i + j * word_len:i + (j + 1) * word_len]
            
            if word not in word_freq:
                break
                
            seen[word] += 1
            if seen[word] > word_freq[word]:
                break
                
            j += 1
            
        if j == word_count:
            result.append(i)
    
    return result

Java Solution


class Solution {
    public List findSubstring(String s, String[] words) {
        List result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }
        
        Map wordFreq = new HashMap<>();
        for (String word : words) {
            wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
        }
        
        int wordLen = words[0].length();
        int wordCount = words.length;
        int totalLen = wordLen * wordCount;
        
        for (int i = 0; i <= s.length() - totalLen; i++) {
            Map seen = new HashMap<>();
            int j;
            
            for (j = 0; j < wordCount; j++) {
                int start = i + j * wordLen;
                String word = s.substring(start, start + wordLen);
                
                if (!wordFreq.containsKey(word)) {
                    break;
                }
                
                seen.put(word, seen.getOrDefault(word, 0) + 1);
                if (seen.get(word) > wordFreq.get(word)) {
                    break;
                }
            }
            
            if (j == wordCount) {
                result.add(i);
            }
        }
        
        return result;
    }
}

C++ Solution


class Solution {
public:
    vector findSubstring(string s, vector& words) {
        vector result;
        if (s.empty() || words.empty()) {
            return result;
        }
        
        unordered_map wordFreq;
        for (const string& word : words) {
            wordFreq[word]++;
        }
        
        int wordLen = words[0].length();
        int wordCount = words.size();
        int totalLen = wordLen * wordCount;
        
        for (int i = 0; i <= s.length() - totalLen; i++) {
            unordered_map seen;
            int j;
            
            for (j = 0; j < wordCount; j++) {
                string word = s.substr(i + j * wordLen, wordLen);
                
                if (wordFreq.find(word) == wordFreq.end()) {
                    break;
                }
                
                seen[word]++;
                if (seen[word] > wordFreq[word]) {
                    break;
                }
            }
            
            if (j == wordCount) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

JavaScript Solution


/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if (!s || !words.length) return [];
    
    const result = [];
    const wordLen = words[0].length;
    const wordCount = words.length;
    const totalLen = wordLen * wordCount;
    const wordFreq = new Map();
    
    // Count word frequencies
    for (const word of words) {
        wordFreq.set(word, (wordFreq.get(word) || 0) + 1);
    }
    
    for (let i = 0; i <= s.length - totalLen; i++) {
        const seen = new Map();
        let j;
        
        for (j = 0; j < wordCount; j++) {
            const start = i + j * wordLen;
            const word = s.slice(start, start + wordLen);
            
            if (!wordFreq.has(word)) break;
            
            seen.set(word, (seen.get(word) || 0) + 1);
            if (seen.get(word) > wordFreq.get(word)) break;
        }
        
        if (j === wordCount) result.push(i);
    }
    
    return result;
};

C# Solution


public class Solution {
    public IList FindSubstring(string s, string[] words) {
        var result = new List();
        if (string.IsNullOrEmpty(s) || words == null || words.Length == 0) {
            return result;
        }
        
        var wordFreq = new Dictionary();
        foreach (var word in words) {
            if (!wordFreq.ContainsKey(word)) {
                wordFreq[word] = 0;
            }
            wordFreq[word]++;
        }
        
        int wordLen = words[0].Length;
        int wordCount = words.Length;
        int totalLen = wordLen * wordCount;
        
        for (int i = 0; i <= s.Length - totalLen; i++) {
            var seen = new Dictionary();
            int j;
            
            for (j = 0; j < wordCount; j++) {
                int start = i + j * wordLen;
                string word = s.Substring(start, wordLen);
                
                if (!wordFreq.ContainsKey(word)) {
                    break;
                }
                
                if (!seen.ContainsKey(word)) {
                    seen[word] = 0;
                }
                seen[word]++;
                
                if (seen[word] > wordFreq[word]) {
                    break;
                }
            }
            
            if (j == wordCount) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n * m * k) where n is the length of string s, m is the length of each word, and k is the number of words
Space Complexity: O(k) for storing word frequencies

Solution Explanation

This solution uses a sliding window approach with hash maps. Here's how it works:

Create a frequency map of all words
For each possible starting position:
- Try to match all words in any order
- Keep track of seen words and their frequencies
- If all words are matched, add the starting index

Key points:

All words are of the same length
Words can be used only once
Order of words doesn't matter
Handle edge cases (empty string, empty words array)