Substring with Concatenation of All Words

Problem Statement

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

A concatenated string is a string that exactly contains all the strings of words concatenated in any order and without overlapping.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

What to notice first

• Each word in words has the same length — this is critical for the sliding window approach.
• Words can appear multiple times in words, and the concatenation must use all of them, including duplicates.
• We are looking for starting indices, not the substrings themselves.
• The total length of a valid concatenation is always len(word) * len(words).

Examples

Input String	Words	Output	Explanation
"barfoothefoobarman"	["foo","bar"]	[0, 9]	Index 0: “barfoo” is “bar” + “foo”. Index 9: “foobarman”[0:6] = “foobar” is “foo” + “bar”.
"wordgoodgoodgoodbestword"	["word","good","best","word"]	[]	No substring matches the concatenation.
"barfoofoobarthefoobarman"	["bar","foo","the"]	[6, 9, 12]	Index 6: “barfoo” is “bar”+“foo”. Index 9: “foobar” is “foo”+“bar”. Index 12: “thefo…”

Constraints

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• s and words[i] consist of lowercase English letters
• All the strings of words are of the same length

Real-World Applications

Where this pattern appears

• URL path parsing — break a URL slug into known path segments to validate request routing.
• Command-line parsing — extract command tokens that match a known set of subcommands.
• DNA sequence matching — find regions where a sequence contains all required genetic markers concatenated in any order.
• Log format validation — verify that a log entry contains all required field values in any sequence.
• Tokenization in compiler design — verify that a source code token stream matches an expected pattern.

Complexity Comparison

Approach	Time	Space	Best When
Sliding Window	O(n * m)	O(m * k)	General case — trades some constant-factor overhead for simplicity
Brute Force	O(n² * m)	O(m * k)	Input is tiny, academic purposes

where n = len(s), m = len(words), k = average word length

Which approach should you learn first?

• Pick Sliding Window if you want the optimal practical solution — it efficiently checks every valid window.
• Pick Brute Force if you are learning the problem from scratch and want to understand the concept before optimization.

Best For Speed

Sliding Window

O(nm) time · O(mk) space

Learning

Brute Force

O(n²m) time · O(mk) space

Approach 1: Sliding Window with Hash Map (Recommended)

★ Recommended

For each possible starting position in the string, check if the next len(word) * len(words) characters form a valid concatenation of all words. Maintain a hash map to count word frequencies in the current window and compare against the expected frequency map.

The key insight is that because all words have the same length, we can divide any substring of that total length into fixed chunks and check if they match our word set.

⏱ Time O(n*m) Each position checked once, m words extracted per check 💾 Space O(m*k) Hash map stores unique words

Step-by-step Example

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

• Word length: 3
• Total concatenation length: 3 * 2 = 6
• Expected frequencies: {foo: 1, bar: 1}

Index	Window	Words	Frequencies	Match?
0	”barfoo”	[“bar”,“foo”]	bar:1, foo:1	✓
3	”foothef”	[“foo”,“the”,“f”]	No valid split	✗
9	”foobar”	[“foo”,“bar”]	foo:1, bar:1	✓

Animated walkthrough

How the sliding window checks each position

Watch the window slide over the string, extract words of fixed length, count frequencies, and compare against the expected pattern.

Back Autoplay Next Reset

Step 1 of 3 Target: 6

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function findSubstringWindow(s, words):
    if words.empty() or s.empty():
        return []

    wordLen = len(words[0])
    wordCount = len(words)
    totalLen = wordLen * wordCount

    // Build frequency map of words
    wordFreq = {}
    for word in words:
        wordFreq[word] += 1

    result = []

    // Check every possible starting position
    for i from 0 to len(s) - totalLen:
        // Extract words from this window
        windowFreq = {}
        for j from 0 to wordCount - 1:
            word = s[i + j*wordLen : i + (j+1)*wordLen]
            windowFreq[word] += 1

        // Compare frequencies
        if windowFreq == wordFreq:
            result.append(i)

    return result

Solution Code

Python

substring_with_concatenation_of_all_words_sliding_window.py

from typing import List
from collections import defaultdict


def find_substring_sliding_window(s: str, words: List[str]) -> List[int]:
    """
    Find all starting indices of substrings that are concatenations of all words.

    Uses sliding window with word frequency tracking.
    Time: O(n * m), where n = len(s), m = len(words)
    Space: O(m * k), where k = average word length
    """
    if not words or not s:
        return []

    word_len = len(words[0])
    word_count = len(words)
    total_len = word_len * word_count

    # Count frequency of each word
    word_freq = defaultdict(int)
    for word in words:
        word_freq[word] += 1

    result = []

    # For each possible starting position
    for i in range(len(s) - total_len + 1):
        # Check if substring starting at i is a concatenation
        window_freq = defaultdict(int)

        # Extract and count words in this window
        for j in range(word_count):
            word = s[i + j * word_len:i + (j + 1) * word_len]
            window_freq[word] += 1

        # Check if frequencies match
        if window_freq == word_freq:
            result.append(i)

    return result


# Test cases
if __name__ == "__main__":
    # Example 1
    s1 = "barfoothefoobarman"
    words1 = ["foo", "bar"]
    print(find_substring_sliding_window(s1, words1))  # [0, 9]

    # Example 2
    s2 = "wordgoodgoodgoodbestword"
    words2 = ["word", "good", "best", "word"]
    print(find_substring_sliding_window(s2, words2))  # []

    # Example 3
    s3 = "barfoofoobarthefoobarman"
    words3 = ["bar", "foo", "the"]
    print(find_substring_sliding_window(s3, words3))  # [6, 9, 12]

C++

substring_with_concatenation_of_all_words_sliding_window.cpp

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

std::vector<int> findSubstringWindowApproach(
    const std::string& s,
    const std::vector<std::string>& words) {
    if (words.empty() || s.empty()) {
        return {};
    }

    int wordLen = words[0].length();
    int wordCount = words.size();
    int totalLen = wordLen * wordCount;

    // Count frequency of each word
    std::unordered_map<std::string, int> wordFreq;
    for (const auto& word : words) {
        wordFreq[word]++;
    }

    std::vector<int> result;

    // For each possible starting position
    for (int i = 0; i <= (int)s.length() - totalLen; i++) {
        std::unordered_map<std::string, int> windowFreq;

        // Extract and count words in this window
        for (int j = 0; j < wordCount; j++) {
            std::string word = s.substr(i + j * wordLen, wordLen);
            windowFreq[word]++;
        }

        // Check if frequencies match
        if (windowFreq == wordFreq) {
            result.push_back(i);
        }
    }

    return result;
}

int main() {
    // Example 1
    std::string s1 = "barfoothefoobarman";
    std::vector<std::string> words1 = {"foo", "bar"};
    std::vector<int> result1 = findSubstringWindowApproach(s1, words1);
    std::cout << "Example 1: ";
    for (int idx : result1) {
        std::cout << idx << " ";
    }
    std::cout << std::endl; // [0, 9]

    // Example 2
    std::string s2 = "wordgoodgoodgoodbestword";
    std::vector<std::string> words2 = {"word", "good", "best", "word"};
    std::vector<int> result2 = findSubstringWindowApproach(s2, words2);
    std::cout << "Example 2: ";
    for (int idx : result2) {
        std::cout << idx << " ";
    }
    std::cout << std::endl; // []

    // Example 3
    std::string s3 = "barfoofoobarthefoobarman";
    std::vector<std::string> words3 = {"bar", "foo", "the"};
    std::vector<int> result3 = findSubstringWindowApproach(s3, words3);
    std::cout << "Example 3: ";
    for (int idx : result3) {
        std::cout << idx << " ";
    }
    std::cout << std::endl; // [6, 9, 12]

    return 0;
}

Java

substring_with_concatenation_of_all_words_sliding_window.java

import java.util.*;

public class SubstringWithConcatenationOfAllWordsSlidingWindow {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();

        if (words == null || words.length == 0 || s == null || s.length() == 0) {
            return result;
        }

        int wordLen = words[0].length();
        int wordCount = words.length;
        int totalLen = wordLen * wordCount;

        // Count frequency of each word
        Map<String, Integer> wordFreq = new HashMap<>();
        for (String word : words) {
            wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
        }

        // For each possible starting position
        for (int i = 0; i <= s.length() - totalLen; i++) {
            Map<String, Integer> windowFreq = new HashMap<>();

            // Extract and count words in this window
            for (int j = 0; j < wordCount; j++) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                windowFreq.put(word, windowFreq.getOrDefault(word, 0) + 1);
            }

            // Check if frequencies match
            if (windowFreq.equals(wordFreq)) {
                result.add(i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // Example 1
        String s1 = "barfoothefoobarman";
        String[] words1 = {"foo", "bar"};
        System.out.println(findSubstring(s1, words1)); // [0, 9]

        // Example 2
        String s2 = "wordgoodgoodgoodbestword";
        String[] words2 = {"word", "good", "best", "word"};
        System.out.println(findSubstring(s2, words2)); // []

        // Example 3
        String s3 = "barfoofoobarthefoobarman";
        String[] words3 = {"bar", "foo", "the"};
        System.out.println(findSubstring(s3, words3)); // [6, 9, 12]
    }
}

JavaScript

substring_with_concatenation_of_all_words_sliding_window.js

function findSubstring(s, words) {
    const result = [];

    if (!words || words.length === 0 || !s || s.length === 0) {
        return result;
    }

    const wordLen = words[0].length;
    const wordCount = words.length;
    const totalLen = wordLen * wordCount;

    // Count frequency of each word
    const wordFreq = {};
    for (const word of words) {
        wordFreq[word] = (wordFreq[word] || 0) + 1;
    }

    // Helper to compare two frequency maps
    const frequenciesMatch = (freq1, freq2) => {
        const keys1 = Object.keys(freq1).sort();
        const keys2 = Object.keys(freq2).sort();
        if (keys1.length !== keys2.length) return false;
        for (let i = 0; i < keys1.length; i++) {
            if (keys1[i] !== keys2[i] || freq1[keys1[i]] !== freq2[keys1[i]]) {
                return false;
            }
        }
        return true;
    };

    // For each possible starting position
    for (let i = 0; i <= s.length - totalLen; i++) {
        const windowFreq = {};

        // Extract and count words in this window
        for (let j = 0; j < wordCount; j++) {
            const word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
            windowFreq[word] = (windowFreq[word] || 0) + 1;
        }

        // Check if frequencies match
        if (frequenciesMatch(windowFreq, wordFreq)) {
            result.push(i);
        }
    }

    return result;
}

// Test cases
console.log(findSubstring("barfoothefoobarman", ["foo", "bar"]));          // [0, 9]
console.log(findSubstring("wordgoodgoodgoodbestword", ["word", "good", "best", "word"])); // []
console.log(findSubstring("barfoofoobarthefoobarman", ["bar", "foo", "the"])); // [6, 9, 12]

Rust

substring_with_concatenation_of_all_words_sliding_window.rs

use std::collections::HashMap;

fn find_substring_window_approach(s: &str, words: Vec<&str>) -> Vec<i32> {
    if words.is_empty() || s.is_empty() {
        return vec![];
    }

    let word_len = words[0].len();
    let word_count = words.len();
    let total_len = word_len * word_count;

    // Count frequency of each word
    let mut word_freq: HashMap<&str, i32> = HashMap::new();
    for word in &words {
        *word_freq.entry(word).or_insert(0) += 1;
    }

    let mut result = vec![];

    // For each possible starting position
    for i in 0..=(s.len().saturating_sub(total_len)) {
        let mut window_freq: HashMap<&str, i32> = HashMap::new();

        // Extract and count words in this window
        for j in 0..word_count {
            let start = i + j * word_len;
            let end = start + word_len;
            if end <= s.len() {
                let word = &s[start..end];
                *window_freq.entry(word).or_insert(0) += 1;
            }
        }

        // Check if frequencies match
        if window_freq == word_freq {
            result.push(i as i32);
        }
    }

    result
}

fn main() {
    // Example 1
    let s1 = "barfoothefoobarman";
    let words1 = vec!["foo", "bar"];
    println!("{:?}", find_substring_window_approach(s1, words1)); // [0, 9]

    // Example 2
    let s2 = "wordgoodgoodgoodbestword";
    let words2 = vec!["word", "good", "best", "word"];
    println!("{:?}", find_substring_window_approach(s2, words2)); // []

    // Example 3
    let s3 = "barfoofoobarthefoobarman";
    let words3 = vec!["bar", "foo", "the"];
    println!("{:?}", find_substring_window_approach(s3, words3)); // [6, 9, 12]
}

Go

substring_with_concatenation_of_all_words_sliding_window.go

package main

import (
  "fmt"
)

func findSubstringWindowApproach(s string, words []string) []int {
  var result []int

  if len(words) == 0 || len(s) == 0 {
    return result
  }

  wordLen := len(words[0])
  wordCount := len(words)
  totalLen := wordLen * wordCount

  // Count frequency of each word
  wordFreq := make(map[string]int)
  for _, word := range words {
    wordFreq[word]++
  }

  // For each possible starting position
  for i := 0; i <= len(s)-totalLen; i++ {
    windowFreq := make(map[string]int)

    // Extract and count words in this window
    for j := 0; j < wordCount; j++ {
      start := i + j*wordLen
      end := start + wordLen
      word := s[start:end]
      windowFreq[word]++
    }

    // Check if frequencies match
    if mapsEqual(windowFreq, wordFreq) {
      result = append(result, i)
    }
  }

  return result
}

// Helper function to compare two maps
func mapsEqual(m1, m2 map[string]int) bool {
  if len(m1) != len(m2) {
    return false
  }
  for key, val := range m1 {
    if m2[key] != val {
      return false
    }
  }
  return true
}

func main() {
  // Example 1
  s1 := "barfoothefoobarman"
  words1 := []string{"foo", "bar"}
  fmt.Println(findSubstringWindowApproach(s1, words1)) // [0, 9]

  // Example 2
  s2 := "wordgoodgoodgoodbestword"
  words2 := []string{"word", "good", "best", "word"}
  fmt.Println(findSubstringWindowApproach(s2, words2)) // []

  // Example 3
  s3 := "barfoofoobarthefoobarman"
  words3 := []string{"bar", "foo", "the"}
  fmt.Println(findSubstringWindowApproach(s3, words3)) // [6, 9, 12]
}

Approach 2: Brute Force

✓ Simple

For each starting position, extract the window substring and manually check if it can be decomposed into the word list. Iterate through the substring in word-sized chunks, remove matching words from a copy of the word list, and verify all words are consumed.

This approach is less efficient but easier to understand conceptually.

⏱ Time O(n²*m) Nested loops with list operations 💾 Space O(m*k) Temporary word lists

Step-by-step Example

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

Index	Window	Temp Words	Status
0	”barfoo”	Extract “bar” → remove → [“foo”]. Extract “foo” → remove → [].	✓ Match
1	”arfoot”	Extract “arf” → not in list.	✗ No match
9	”foobar”	Extract “foo” → remove → [“bar”]. Extract “bar” → remove → [].	✓ Match

Pseudocode

function findSubstringBruteForce(s, words):
    if words.empty() or s.empty():
        return []

    wordLen = len(words[0])
    wordCount = len(words)
    totalLen = wordLen * wordCount

    result = []

    // Check every possible starting position
    for i from 0 to len(s) - totalLen:
        substring = s[i : i + totalLen]
        tempWords = copy(words)
        valid = true

        // Try to match all words in this window
        for j from 0 to wordCount - 1:
            word = substring[j*wordLen : (j+1)*wordLen]
            if word in tempWords:
                remove word from tempWords
            else:
                valid = false
                break

        if valid and tempWords.empty():
            result.append(i)

    return result

Solution Code

Python

substring_with_concatenation_of_all_words_brute_force.py

from typing import List
from collections import Counter
from itertools import permutations


def find_substring_brute_force(s: str, words: List[str]) -> List[int]:
    """
    Find all starting indices of substrings that are concatenations of all words.

    Uses brute force by checking every possible concatenation.
    Time: O(n² * m), where n = len(s), m = len(words)
    Space: O(m * k), where k = average word length
    """
    if not words or not s:
        return []

    word_len = len(words[0])
    word_count = len(words)
    total_len = word_len * word_count

    result = []

    # For each possible starting position in the string
    for i in range(len(s) - total_len + 1):
        # Extract the substring of exact length
        substring = s[i:i + total_len]

        # Check if this substring can be formed by concatenating all words
        temp_words = words[:]
        valid = True

        for j in range(word_count):
            word = substring[j * word_len:(j + 1) * word_len]
            if word in temp_words:
                temp_words.remove(word)
            else:
                valid = False
                break

        if valid and not temp_words:
            result.append(i)

    return result


# Test cases
if __name__ == "__main__":
    # Example 1
    s1 = "barfoothefoobarman"
    words1 = ["foo", "bar"]
    print(find_substring_brute_force(s1, words1))  # [0, 9]

    # Example 2
    s2 = "wordgoodgoodgoodbestword"
    words2 = ["word", "good", "best", "word"]
    print(find_substring_brute_force(s2, words2))  # []

    # Example 3
    s3 = "barfoofoobarthefoobarman"
    words3 = ["bar", "foo", "the"]
    print(find_substring_brute_force(s3, words3))  # [6, 9, 12]

C++

substring_with_concatenation_of_all_words_brute_force.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> findSubstringBruteForce(
    const std::string& s,
    std::vector<std::string> words) {
    if (words.empty() || s.empty()) {
        return {};
    }

    int wordLen = words[0].length();
    int wordCount = words.size();
    int totalLen = wordLen * wordCount;

    std::vector<int> result;

    // For each possible starting position in the string
    for (int i = 0; i <= (int)s.length() - totalLen; i++) {
        // Extract the substring of exact length
        std::string substring = s.substr(i, totalLen);

        // Check if this substring can be formed by concatenating all words
        std::vector<std::string> tempWords = words;
        bool valid = true;

        for (int j = 0; j < wordCount; j++) {
            std::string word = substring.substr(j * wordLen, wordLen);
            auto it = std::find(tempWords.begin(), tempWords.end(), word);
            if (it != tempWords.end()) {
                tempWords.erase(it);
            } else {
                valid = false;
                break;
            }
        }

        if (valid && tempWords.empty()) {
            result.push_back(i);
        }
    }

    return result;
}

int main() {
    // Example 1
    std::string s1 = "barfoothefoobarman";
    std::vector<std::string> words1 = {"foo", "bar"};
    std::vector<int> result1 = findSubstringBruteForce(s1, words1);
    std::cout << "Example 1: ";
    for (int idx : result1) {
        std::cout << idx << " ";
    }
    std::cout << std::endl; // [0, 9]

    // Example 2
    std::string s2 = "wordgoodgoodgoodbestword";
    std::vector<std::string> words2 = {"word", "good", "best", "word"};
    std::vector<int> result2 = findSubstringBruteForce(s2, words2);
    std::cout << "Example 2: ";
    for (int idx : result2) {
        std::cout << idx << " ";
    }
    std::cout << std::endl; // []

    // Example 3
    std::string s3 = "barfoofoobarthefoobarman";
    std::vector<std::string> words3 = {"bar", "foo", "the"};
    std::vector<int> result3 = findSubstringBruteForce(s3, words3);
    std::cout << "Example 3: ";
    for (int idx : result3) {
        std::cout << idx << " ";
    }
    std::cout << std::endl; // [6, 9, 12]

    return 0;
}

Java

substring_with_concatenation_of_all_words_brute_force.java

import java.util.*;

public class SubstringWithConcatenationOfAllWordsBruteForce {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();

        if (words == null || words.length == 0 || s == null || s.length() == 0) {
            return result;
        }

        int wordLen = words[0].length();
        int wordCount = words.length;
        int totalLen = wordLen * wordCount;

        // For each possible starting position in the string
        for (int i = 0; i <= s.length() - totalLen; i++) {
            // Extract the substring of exact length
            String substring = s.substring(i, i + totalLen);

            // Check if this substring can be formed by concatenating all words
            List<String> tempWords = new ArrayList<>(Arrays.asList(words));
            boolean valid = true;

            for (int j = 0; j < wordCount; j++) {
                String word = substring.substring(j * wordLen, (j + 1) * wordLen);
                if (tempWords.contains(word)) {
                    tempWords.remove(word);
                } else {
                    valid = false;
                    break;
                }
            }

            if (valid && tempWords.isEmpty()) {
                result.add(i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // Example 1
        String s1 = "barfoothefoobarman";
        String[] words1 = {"foo", "bar"};
        System.out.println(findSubstring(s1, words1)); // [0, 9]

        // Example 2
        String s2 = "wordgoodgoodgoodbestword";
        String[] words2 = {"word", "good", "best", "word"};
        System.out.println(findSubstring(s2, words2)); // []

        // Example 3
        String s3 = "barfoofoobarthefoobarman";
        String[] words3 = {"bar", "foo", "the"};
        System.out.println(findSubstring(s3, words3)); // [6, 9, 12]
    }
}

JavaScript

substring_with_concatenation_of_all_words_brute_force.js

function findSubstring(s, words) {
    const result = [];

    if (!words || words.length === 0 || !s || s.length === 0) {
        return result;
    }

    const wordLen = words[0].length;
    const wordCount = words.length;
    const totalLen = wordLen * wordCount;

    // For each possible starting position in the string
    for (let i = 0; i <= s.length - totalLen; i++) {
        // Extract the substring of exact length
        const substring = s.substring(i, i + totalLen);

        // Check if this substring can be formed by concatenating all words
        const tempWords = [...words];
        let valid = true;

        for (let j = 0; j < wordCount; j++) {
            const word = substring.substring(j * wordLen, (j + 1) * wordLen);
            const idx = tempWords.indexOf(word);
            if (idx !== -1) {
                tempWords.splice(idx, 1);
            } else {
                valid = false;
                break;
            }
        }

        if (valid && tempWords.length === 0) {
            result.push(i);
        }
    }

    return result;
}

// Test cases
console.log(findSubstring("barfoothefoobarman", ["foo", "bar"]));          // [0, 9]
console.log(findSubstring("wordgoodgoodgoodbestword", ["word", "good", "best", "word"])); // []
console.log(findSubstring("barfoofoobarthefoobarman", ["bar", "foo", "the"])); // [6, 9, 12]

Rust

substring_with_concatenation_of_all_words_brute_force.rs

fn find_substring_brute_force(s: &str, words: Vec<&str>) -> Vec<i32> {
    if words.is_empty() || s.is_empty() {
        return vec![];
    }

    let word_len = words[0].len();
    let word_count = words.len();
    let total_len = word_len * word_count;

    let mut result = vec![];

    // For each possible starting position in the string
    for i in 0..=(s.len().saturating_sub(total_len)) {
        // Extract the substring of exact length
        if i + total_len > s.len() {
            break;
        }
        let substring = &s[i..i + total_len];

        // Check if this substring can be formed by concatenating all words
        let mut temp_words = words.clone();
        let mut valid = true;

        for j in 0..word_count {
            let start = j * word_len;
            let end = start + word_len;
            let word = &substring[start..end];

            if let Some(pos) = temp_words.iter().position(|&w| w == word) {
                temp_words.remove(pos);
            } else {
                valid = false;
                break;
            }
        }

        if valid && temp_words.is_empty() {
            result.push(i as i32);
        }
    }

    result
}

fn main() {
    // Example 1
    let s1 = "barfoothefoobarman";
    let words1 = vec!["foo", "bar"];
    println!("{:?}", find_substring_brute_force(s1, words1)); // [0, 9]

    // Example 2
    let s2 = "wordgoodgoodgoodbestword";
    let words2 = vec!["word", "good", "best", "word"];
    println!("{:?}", find_substring_brute_force(s2, words2)); // []

    // Example 3
    let s3 = "barfoofoobarthefoobarman";
    let words3 = vec!["bar", "foo", "the"];
    println!("{:?}", find_substring_brute_force(s3, words3)); // [6, 9, 12]
}

Go

substring_with_concatenation_of_all_words_brute_force.go

package main

import (
  "fmt"
)

func findSubstringBruteForce(s string, words []string) []int {
  var result []int

  if len(words) == 0 || len(s) == 0 {
    return result
  }

  wordLen := len(words[0])
  wordCount := len(words)
  totalLen := wordLen * wordCount

  // For each possible starting position in the string
  for i := 0; i <= len(s)-totalLen; i++ {
    // Extract the substring of exact length
    substring := s[i : i+totalLen]

    // Check if this substring can be formed by concatenating all words
    tempWords := make([]string, len(words))
    copy(tempWords, words)
    valid := true

    for j := 0; j < wordCount; j++ {
      start := j * wordLen
      end := start + wordLen
      word := substring[start:end]

      found := false
      for k, w := range tempWords {
        if w == word {
          tempWords = append(tempWords[:k], tempWords[k+1:]...)
          found = true
          break
        }
      }

      if !found {
        valid = false
        break
      }
    }

    if valid && len(tempWords) == 0 {
      result = append(result, i)
    }
  }

  return result
}

func main() {
  // Example 1
  s1 := "barfoothefoobarman"
  words1 := []string{"foo", "bar"}
  fmt.Println(findSubstringBruteForce(s1, words1)) // [0, 9]

  // Example 2
  s2 := "wordgoodgoodgoodbestword"
  words2 := []string{"word", "good", "best", "word"}
  fmt.Println(findSubstringBruteForce(s2, words2)) // []

  // Example 3
  s3 := "barfoofoobarthefoobarman"
  words3 := []string{"bar", "foo", "the"}
  fmt.Println(findSubstringBruteForce(s3, words3)) // [6, 9, 12]
}

Common mistakes

Watch for these pitfalls

• Forgetting equal word length — Assuming words can be different lengths. All words have the same length by problem definition; use this!
• Not handling duplicates — If “foo” appears twice in words, both occurrences must be used. Using a frequency map prevents this error.
• Off-by-one in substring bounds — Computing s.substr(i, i + totalLen) instead of the correct slice notation.
• Comparing entire substring instead of word-by-word — This only works if order doesn’t matter, which it doesn’t, but word-level matching is cleaner.
• Confusing index vs. value — The output must be starting indices, not the substrings themselves.

Approach 3: Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

substring_with_concatenation_of_all_words_optimized.py

"""
Solution for Substring with Concatenation of All Words
"""

def solve():
    """Implementation for approach 3 of Substring with Concatenation of All Words"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

substring_with_concatenation_of_all_words_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Substring with Concatenation of All Words
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SubstringWithConcatenationOfAllWordsOptimized.java

/**
 * Solution for Substring with Concatenation of All Words
 * Approach 3
 */
public class SubstringWithConcatenationOfAllWordsOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

substring_with_concatenation_of_all_words_optimized.js

/**
 * Solution for Substring with Concatenation of All Words
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

substring_with_concatenation_of_all_words_optimized.rs

/// Solution for Substring with Concatenation of All Words
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

substring_with_concatenation_of_all_words_optimized.go

package main

import "fmt"

// Solution for Substring with Concatenation of All Words
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Longest Substring Without Repeating Characters ↗ Medium #3
• Minimum Window Substring ↗ Hard #76
• Repeated DNA Sequences ↗ Medium #187

Interview Tips

Key trade-offs to discuss

• Why sliding window over brute force? Linear factor improvement: O(nm) vs O(n²m). For interview, sliding window shows pattern mastery.
• Why use a hash map? Comparing two dictionaries is O(k) where k is unique words. Faster than trying all permutations or using nested loops.
• Equal word length is crucial — This constraint makes the problem tractable. Mention you noticed it and why it matters.
• Edge cases: Empty words array, empty string, words longer than string, duplicate words in the array (must all be used).
• Follow-up — Variable-length words: If words had different lengths, the problem becomes significantly harder (you’d need a trie or backtracking).
• Follow-up — Count matches: If asked to count instead of return indices, only change the return statement.