Concatenated word sequence indices

You are twenty minutes into a Meta phone screen when the interviewer says, "Given a string and a list of words, all the same length, find every position where a permutation of those words appears as a contiguous substring." At first glance it looks like you would need to generate every permutation, but the equal-length constraint is the key that unlocks a much faster approach. This problem is also known as "Substring with Concatenation of All Words" on other platforms, and it regularly appears at companies like Google, Apple, J.P. Morgan, and Uber.

TL;DR

Use a word-level sliding window with two hash maps. One map stores the target word frequencies, the other tracks word frequencies inside the current window. Run wordLength independent passes (one per starting offset) so you cover every valid alignment. Each pass slides left and right pointers in steps of wordLength. When a word is not in the target map, reset the window. When a word count exceeds the target, shrink from the left. When the window spans exactly totalLength characters, record the starting index. This runs in O(n * k) time and O(m) space.

Why This Problem Matters

This problem sits at the intersection of three fundamental interview topics: sliding windows, hash maps, and string processing. Interviewers love it because a naive approach (generate all permutations) is immediately obvious but far too slow, and the candidate has to reason their way to the word-level window insight. It also tests careful implementation. Off-by-one errors, missing edge cases with duplicate words, and forgetting to reset state on invalid words are all common failure modes. If you can solve this cleanly, you demonstrate fluency with the sliding window pattern and hash-based frequency counting, both of which transfer to dozens of other problems.

Understanding the Problem

You have a string s and an array of strings words. Every string in words has the same length. Your goal is to find all starting indices i in s such that the substring s[i..i+totalLength) is some permutation of the words concatenated together, with no gaps or extra characters.

Here is the first example:

findSubstring("barfoothefoobarman", ["foo", "bar"]) should return [0, 9].

At index 0, the substring "barfoo" is "bar" + "foo", a valid permutation. At index 9, the substring "foobar" is "foo" + "bar", also valid.

The second example, findSubstring("wordgoodgoodgoodbestword", ["word","good","best","word"]), returns [] because no window of length 16 (4 words of length 4) contains exactly those four words with the right frequencies.

The third example is richer:

findSubstring("barfoofoobarthefoobarman", ["bar","foo","the"]) returns [6, 9, 12].

Edge Cases

1. Single character words: s = "a", words = ["a"] returns [0]
2. No match: s = "a", words = ["b"] returns []
3. Duplicate words: s = "aaaaaaaa", words = ["aa","aa","aa"] returns [0, 2]
4. String shorter than total word length: return [] immediately

The duplicate words case is particularly tricky. The frequency map must track that "aa" needs to appear exactly three times, not just that it is present.

Solution Approach

Why Permutations Do Not Work

With m words, there are m! permutations. Even for 10 words, that is 3.6 million strings to check against every starting position. The constraint words.length ≤ 4000 makes this approach completely impractical.

The Word-Level Sliding Window

The critical observation is that all words have the same length k. This means any valid concatenation is built from non-overlapping chunks of size k. Instead of comparing character by character, we can compare word by word.

But there is a subtlety: a valid concatenation starting at index i aligns to a specific offset modulo k. If k = 3, a concatenation starting at index 1 is built from chunks [1,4), [4,7), [7,10), and so on. A concatenation starting at index 0 uses a different set of chunks: [0,3), [3,6), [6,9).

So we run k independent passes, one for each starting offset from 0 to k-1.

Within each pass, we maintain a standard sliding window with left and right pointers, both advancing in steps of k. Two hash maps do the bookkeeping:

• wordCountMap: the target frequencies, built once from words
• currentCount: the frequencies inside the current window

Algorithm Steps

For each offset i in [0, k):

1. Set left = i, right = i, clear currentCount
2. While right + k ≤ s.length:
   • Extract word = s[right..right+k)
   • Advance right by k
   • If word is in wordCountMap:
     • Increment currentCount[word]
     • While currentCount[word] exceeds wordCountMap[word], shrink from the left by extracting the leftmost word, decrementing its count, and advancing left by k
     • If right - left == totalLength, record left as a match
   • Else: clear currentCount, set left = right (skip past the invalid word)
3. Sort and return the collected indices

Here is the window state evolving for offset 0 on the first example:

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    if (s == null || s.isEmpty() || words == null || words.length == 0) {
      return result;
    }

    int wordLength = words[0].length();
    int wordCount = words.length;
    int totalLength = wordLength * wordCount;

    if (s.length() < totalLength) {
      return result;
    }

    // Build target frequency map
    Map<String, Integer> wordCountMap = new HashMap<>();
    for (String word : words) {
      wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) + 1);
    }

    // Run one pass per starting offset
    for (int offset = 0; offset < wordLength; offset++) {
      int left = offset;
      int right = offset;
      Map<String, Integer> currentCount = new HashMap<>();

      while (right + wordLength <= s.length()) {
        String word = s.substring(right, right + wordLength);
        right += wordLength;

        if (wordCountMap.containsKey(word)) {
          currentCount.put(word, currentCount.getOrDefault(word, 0) + 1);

          // Shrink window if this word appears too many times
          while (currentCount.get(word) > wordCountMap.get(word)) {
            String leftWord = s.substring(left, left + wordLength);
            currentCount.put(leftWord, currentCount.get(leftWord) - 1);
            left += wordLength;
          }

          // Check if window covers exactly totalLength characters
          if (right - left == totalLength) {
            result.add(left);
          }
        } else {
          // Invalid word: reset window
          currentCount.clear();
          left = right;
        }
      }
    }

    Collections.sort(result);
    return result;
  }
}

Here are the key decisions in this implementation.

The outer loop over offsets ensures every valid alignment is checked. Without it, starting at offset 0 only, we would miss concatenations that begin at positions like 1, 2, or any non-multiple of wordLength.

The inner while loop is the standard sliding window. The right pointer always moves forward by one word. If the word is valid, we add it to currentCount. If the word is not in our target, we know no valid concatenation can include this position, so we jump left past it and clear the map.

The shrink step handles the case where a word appears in the target but we have seen it too many times. We pop words from the left until the count is back in range. This also naturally handles the transition from one valid window to the next, since the leftmost word slides out and gets decremented.

The match check right - left == totalLength works because the window only contains valid target words (invalid words trigger a reset) and no word exceeds its allowed count (the shrink step guarantees this). So if the window is exactly the right size, every word appears at its required frequency.

Complexity Analysis

Time Complexity: O(n * k)

We run k passes (where k = wordLength). In each pass, right advances from offset to at most n in steps of k, visiting at most n/k positions. For each position, we extract a substring of length k in O(k) time. The left pointer also advances monotonically, so across the entire pass, total substring extractions from the left are also bounded by n/k. Total work per pass: O(n). Total across all passes: O(n * k).

In practice k is small (≤ 20 per the constraints), so this behaves almost linearly.

Space Complexity: O(m)

The two hash maps together hold at most words.length distinct entries. Each key is a string of length k. If we define m as the total character count across all words (words.length * k), the space is O(m). The result list adds O(number of matches) but is bounded by O(n/k) in the worst case.

Common Pitfalls

1. Forgetting the offset loop. Running only one pass from index 0 misses valid concatenations that start at other offsets. This is the most frequent bug I see.

2. Not handling duplicate words. If words = ["foo", "foo"], the frequency map must record "foo": 2, and the window must contain exactly two occurrences of "foo". Using a set instead of a frequency map will produce wrong answers.

3. Off-by-one on the window boundary. The condition is right + wordLength ≤ s.length(), not right + wordLength ≤ s.length() - 1. Getting this wrong causes you to skip the last possible word position.

4. Forgetting to clear state on invalid words. When you encounter a word not in the target map, both currentCount and the position of left must be reset. Forgetting to clear currentCount causes stale data to leak into the next window.

5. Sorting the result. Different offset passes discover matches in different orders. Returning without sorting violates the ascending-order requirement.

Interview Tips

When solving this in an interview:

1. Clarify the constraints. Confirm that all words have the same length. This is the key property that makes the word-level window possible.

2. Start with brute force and optimize. Mention the permutation approach, calculate its complexity, and explain why it is too slow. Then introduce the frequency-map insight: you do not need the exact permutation, just the correct word frequencies.

3. Draw the offset concept. Sketch a string on the whiteboard and mark the word boundaries for offset 0 and offset 1. This makes it immediately clear why multiple passes are needed.

4. Trace through a small example. Walk through "barfoo" with ["foo","bar"] step by step, showing how left and right move and how currentCount evolves.

5. Mention the duplicate-word edge case proactively. Interviewers love to see candidates anticipate problems before they are asked.

Key Takeaways

• The equal-length constraint on words transforms this from a permutation problem into a frequency-counting problem. Recognizing this shift is the core insight.
• Running wordLength independent passes ensures every valid alignment is checked. Each pass slides a window in word-sized steps.
• Two frequency maps (target and current) let you verify a match in O(1) per window adjustment. The shrink step keeps the window valid without rebuilding the map.
• Duplicate words require frequency tracking, not just presence tracking. A set is not enough.
• In interviews, start by explaining why brute force fails, then walk through the offset concept visually before writing code.

Practice Makes Perfect

Once you are comfortable with this problem, try these related challenges to solidify your sliding window and hash map skills:

• Longest substring without repeated characters
• Minimum window substring
• Find all anagrams in a string
• Maximum sum sub-array of size K

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Consistent practice with problems like this one, where the naive approach is obvious but the optimal solution requires a genuine insight, is what separates candidates who pass from those who do not.

Solutions in Other Languages

Python

from typing import List
from collections import Counter

class Solution:
    def find_substring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []

        word_length = len(words[0])
        num_words = len(words)
        total_length = word_length * num_words
        word_count = Counter(words)
        result = []

        for i in range(word_length):
            left = i
            right = i
            current_count = Counter()

            while right + word_length <= len(s):
                word = s[right:right + word_length]
                right += word_length

                if word in word_count:
                    current_count[word] += 1

                    while current_count[word] > word_count[word]:
                        left_word = s[left:left + word_length]
                        current_count[left_word] -= 1
                        left += word_length

                    if right - left == total_length:
                        result.append(left)
                else:
                    current_count.clear()
                    left = right

        result.sort()
        return result

JavaScript

class Solution {
  findSubstring(s, words) {
    if (!s || words.length === 0) return [];

    const wordLength = words[0].length;
    const wordCount = words.length;
    const totalLength = wordLength * wordCount;

    if (s.length < totalLength) return [];

    const wordCountMap = new Map();
    for (const word of words) {
      wordCountMap.set(word, (wordCountMap.get(word) || 0) + 1);
    }

    const result = [];

    for (let offset = 0; offset < wordLength; offset++) {
      let left = offset;
      let right = offset;
      const currentCount = new Map();

      while (right + wordLength <= s.length) {
        const word = s.substring(right, right + wordLength);
        right += wordLength;

        if (wordCountMap.has(word)) {
          currentCount.set(word, (currentCount.get(word) || 0) + 1);

          while (currentCount.get(word) > wordCountMap.get(word)) {
            const leftWord = s.substring(left, left + wordLength);
            currentCount.set(leftWord, currentCount.get(leftWord) - 1);
            left += wordLength;
          }

          if (right - left === totalLength) {
            result.push(left);
          }
        } else {
          currentCount.clear();
          left = right;
        }
      }
    }

    result.sort((a, b) => a - b);
    return result;
  }
}

TypeScript

class Solution {
  findSubstring(s: string, words: string[]): number[] {
    if (!s || words.length === 0) return [];

    const wordLength = words[0].length;
    const wordCount = words.length;
    const totalLength = wordLength * wordCount;

    if (s.length < totalLength) return [];

    const wordCountMap = new Map<string, number>();
    for (const word of words) {
      wordCountMap.set(word, (wordCountMap.get(word) || 0) + 1);
    }

    const result: number[] = [];

    for (let offset = 0; offset < wordLength; offset++) {
      let left = offset;
      let right = offset;
      const currentCount = new Map<string, number>();

      while (right + wordLength <= s.length) {
        const word = s.substring(right, right + wordLength);
        right += wordLength;

        if (wordCountMap.has(word)) {
          currentCount.set(word, (currentCount.get(word) || 0) + 1);

          while (currentCount.get(word)! > wordCountMap.get(word)!) {
            const leftWord = s.substring(left, left + wordLength);
            currentCount.set(leftWord, currentCount.get(leftWord)! - 1);
            left += wordLength;
          }

          if (right - left === totalLength) {
            result.push(left);
          }
        } else {
          currentCount.clear();
          left = right;
        }
      }
    }

    result.sort((a, b) => a - b);
    return result;
  }
}

C++

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<int> findSubstring(std::string s, std::vector<std::string> &words) {
        std::vector<int> result;
        if (words.empty() || s.empty()) return result;

        int wordLength = words[0].size();
        int wordCount = words.size();
        int totalLength = wordLength * wordCount;

        if (s.size() < totalLength) return result;

        std::unordered_map<std::string, int> wordCountMap;
        for (const auto& word : words) {
            wordCountMap[word]++;
        }

        for (int offset = 0; offset < wordLength; ++offset) {
            int left = offset;
            int right = offset;
            std::unordered_map<std::string, int> currentCount;

            while (right + wordLength <= s.size()) {
                std::string word = s.substr(right, wordLength);
                right += wordLength;

                if (wordCountMap.find(word) != wordCountMap.end()) {
                    currentCount[word]++;

                    while (currentCount[word] > wordCountMap[word]) {
                        std::string leftWord = s.substr(left, wordLength);
                        currentCount[leftWord]--;
                        left += wordLength;
                    }

                    if (right - left == totalLength) {
                        result.push_back(left);
                    }
                } else {
                    currentCount.clear();
                    left = right;
                }
            }
        }

        std::sort(result.begin(), result.end());
        return result;
    }
};

Go

package solution

import "sort"

func (sol *Solution) FindSubstring(s string, words []string) []int {
    if len(words) == 0 || len(s) == 0 {
        return []int{}
    }

    wordLength := len(words[0])
    wordCount := len(words)
    totalLength := wordLength * wordCount

    if len(s) < totalLength {
        return []int{}
    }

    wordMap := make(map[string]int)
    for _, word := range words {
        wordMap[word]++
    }

    var result []int

    for i := 0; i < wordLength; i++ {
        left := i
        count := 0
        currentMap := make(map[string]int)

        for j := i; j <= len(s)-wordLength; j += wordLength {
            word := s[j : j+wordLength]
            if _, exists := wordMap[word]; exists {
                currentMap[word]++
                count++

                for currentMap[word] > wordMap[word] {
                    leftWord := s[left : left+wordLength]
                    currentMap[leftWord]--
                    count--
                    left += wordLength
                }

                if count == wordCount {
                    result = append(result, left)
                }
            } else {
                currentMap = make(map[string]int)
                count = 0
                left = j + wordLength
            }
        }
    }

    sort.Ints(result)
    return result
}

Scala

class Solution {
  def findSubstring(s: String, words: Array[String]): List[Int] = {
    if (s.isEmpty || words.isEmpty) return List()

    val wordLength = words(0).length
    val wordCount = words.length
    val totalLength = wordLength * wordCount

    if (s.length < totalLength) return List()

    val wordCountMap = words.groupBy(identity).view.mapValues(_.length).toMap
    val resultBuilder = List.newBuilder[Int]

    for (offset <- 0 until wordLength) {
      var left = offset
      var right = offset
      val currentCount = scala.collection.mutable.Map[String, Int]()

      while (right + wordLength <= s.length) {
        val word = s.substring(right, right + wordLength)
        right += wordLength

        if (wordCountMap.contains(word)) {
          currentCount(word) = currentCount.getOrElse(word, 0) + 1

          while (currentCount(word) > wordCountMap(word)) {
            val leftWord = s.substring(left, left + wordLength)
            currentCount(leftWord) = currentCount(leftWord) - 1
            left += wordLength
          }

          if (right - left == totalLength) {
            resultBuilder += left
          }
        } else {
          currentCount.clear()
          left = right
        }
      }
    }

    resultBuilder.result().sorted
  }
}

Kotlin

class Solution {
    fun findSubstring(s: String, words: Array<String>): List<Int> {
        val result = mutableListOf<Int>()
        if (s.isEmpty() || words.isEmpty()) return result

        val wordLength = words[0].length
        val wordCount = words.size
        val totalLength = wordLength * wordCount

        if (s.length < totalLength) return result

        val wordCountMap = mutableMapOf<String, Int>()
        for (word in words) {
            wordCountMap[word] = wordCountMap.getOrDefault(word, 0) + 1
        }

        for (offset in 0 until wordLength) {
            var left = offset
            var right = offset
            val currentCount = mutableMapOf<String, Int>()

            while (right + wordLength <= s.length) {
                val word = s.substring(right, right + wordLength)
                right += wordLength

                if (word in wordCountMap) {
                    currentCount[word] = currentCount.getOrDefault(word, 0) + 1

                    while (currentCount[word]!! > wordCountMap[word]!!) {
                        val leftWord = s.substring(left, left + wordLength)
                        currentCount[leftWord] = currentCount[leftWord]!! - 1
                        left += wordLength
                    }

                    if (right - left == totalLength) {
                        result.add(left)
                    }
                } else {
                    currentCount.clear()
                    left = right
                }
            }
        }

        return result.sorted()
    }
}

Ruby

class Solution
  def find_substring(s, words)
    result = []
    return result if s.nil? || s.empty? || words.nil? || words.empty?

    word_length = words[0].length
    word_count = words.length
    total_length = word_length * word_count

    return result if s.length < total_length

    word_count_map = Hash.new(0)
    words.each { |word| word_count_map[word] += 1 }

    (0...word_length).each do |offset|
      left = offset
      right = offset
      current_count = Hash.new(0)

      while right + word_length <= s.length
        word = s[right, word_length]
        right += word_length

        if word_count_map.key?(word)
          current_count[word] += 1

          while current_count[word] > word_count_map[word]
            left_word = s[left, word_length]
            current_count[left_word] -= 1
            left += word_length
          end

          if right - left == total_length
            result << left
          end
        else
          current_count.clear
          left = right
        end
      end
    end

    result.sort
  end
end

Rust

use std::collections::HashMap;

pub struct Solution;

impl Solution {
    pub fn find_substring(&self, s: String, words: Vec<String>) -> Vec<i32> {
        let mut result: Vec<i32> = Vec::new();
        if s.is_empty() || words.is_empty() {
            return result;
        }

        let word_length = words[0].len();
        let word_count = words.len();
        let total_length = word_length * word_count;

        if s.len() < total_length {
            return result;
        }

        let mut word_count_map: HashMap<&str, i32> = HashMap::new();
        for word in &words {
            *word_count_map.entry(word.as_str()).or_insert(0) += 1;
        }

        for offset in 0..word_length {
            let mut left = offset;
            let mut right = offset;
            let mut current_count: HashMap<&str, i32> = HashMap::new();

            while right + word_length <= s.len() {
                let word = &s[right..right + word_length];
                right += word_length;

                if word_count_map.contains_key(word) {
                    *current_count.entry(word).or_insert(0) += 1;

                    while current_count[word] > word_count_map[word] {
                        let left_word = &s[left..left + word_length];
                        *current_count.get_mut(left_word).unwrap() -= 1;
                        left += word_length;
                    }

                    if right - left == total_length {
                        result.push(left as i32);
                    }
                } else {
                    current_count.clear();
                    left = right;
                }
            }
        }

        result.sort();
        result
    }
}

Swift

import Foundation

class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        var result = [Int]()
        if s.isEmpty || words.isEmpty { return result }

        let chars = Array(s)
        let wordLength = words[0].count
        let wordCount = words.count
        let totalLength = wordLength * wordCount

        if chars.count < totalLength { return result }

        var wordCountMap = [String: Int]()
        for word in words {
            wordCountMap[word, default: 0] += 1
        }

        for offset in 0..<wordLength {
            var left = offset
            var right = offset
            var currentCount = [String: Int]()

            while right + wordLength <= chars.count {
                let word = String(chars[right..<right + wordLength])
                right += wordLength

                if let targetCount = wordCountMap[word] {
                    currentCount[word, default: 0] += 1

                    while currentCount[word]! > targetCount {
                        let leftWord = String(chars[left..<left + wordLength])
                        currentCount[leftWord]! -= 1
                        left += wordLength
                    }

                    if right - left == totalLength {
                        result.append(left)
                    }
                } else {
                    currentCount.removeAll()
                    left = right
                }
            }
        }

        return result.sorted()
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public List<int> FindSubstring(string s, string[] words) {
        var result = new List<int>();
        if (s == null || s.Length == 0 || words == null || words.Length == 0) {
            return result;
        }

        var wordLength = words[0].Length;
        var wordCount = words.Length;
        var totalLength = wordLength * wordCount;

        if (s.Length < totalLength) return result;

        var wordCountMap = new Dictionary<string, int>();
        foreach (var word in words) {
            if (wordCountMap.ContainsKey(word))
                wordCountMap[word]++;
            else
                wordCountMap[word] = 1;
        }

        for (var offset = 0; offset < wordLength; offset++) {
            var left = offset;
            var right = offset;
            var currentCount = new Dictionary<string, int>();

            while (right + wordLength <= s.Length) {
                var currentWord = s.Substring(right, wordLength);
                right += wordLength;

                if (wordCountMap.ContainsKey(currentWord)) {
                    currentCount[currentWord] = currentCount.GetValueOrDefault(currentWord, 0) + 1;

                    while (currentCount[currentWord] > wordCountMap[currentWord]) {
                        var leftWord = s.Substring(left, wordLength);
                        currentCount[leftWord]--;
                        left += wordLength;
                    }

                    if (right - left == totalLength) {
                        result.Add(left);
                    }
                } else {
                    currentCount.Clear();
                    left = right;
                }
            }
        }

        result.Sort();
        return result;
    }
}

Dart

class Solution {
  List<int> findSubstring(String s, List<String> words) {
    List<int> result = [];
    if (s.isEmpty || words.isEmpty) return result;

    int wordLength = words[0].length;
    int wordCount = words.length;
    int totalLength = wordLength * wordCount;

    if (s.length < totalLength) return result;

    Map<String, int> wordCountMap = {};
    for (String word in words) {
      wordCountMap[word] = (wordCountMap[word] ?? 0) + 1;
    }

    for (int offset = 0; offset < wordLength; offset++) {
      int left = offset;
      int right = offset;
      Map<String, int> currentCount = {};

      while (right + wordLength <= s.length) {
        String word = s.substring(right, right + wordLength);
        right += wordLength;

        if (wordCountMap.containsKey(word)) {
          currentCount[word] = (currentCount[word] ?? 0) + 1;

          while (currentCount[word]! > wordCountMap[word]!) {
            String leftWord = s.substring(left, left + wordLength);
            currentCount[leftWord] = currentCount[leftWord]! - 1;
            left += wordLength;
          }

          if (right - left == totalLength) {
            result.add(left);
          }
        } else {
          currentCount.clear();
          left = right;
        }
      }
    }

    result.sort();
    return result;
  }
}

PHP

class Solution {
    public function findSubstring(string $s, array $words): array {
        $result = [];
        if ($s === '' || empty($words)) return $result;

        $wordLength = strlen($words[0]);
        $wordCount = count($words);
        $totalLength = $wordLength * $wordCount;

        if (strlen($s) < $totalLength) return $result;

        $wordCountMap = [];
        foreach ($words as $word) {
            $wordCountMap[$word] = ($wordCountMap[$word] ?? 0) + 1;
        }

        for ($offset = 0; $offset < $wordLength; $offset++) {
            $left = $offset;
            $right = $offset;
            $currentCount = [];

            while ($right + $wordLength <= strlen($s)) {
                $word = substr($s, $right, $wordLength);
                $right += $wordLength;

                if (isset($wordCountMap[$word])) {
                    $currentCount[$word] = ($currentCount[$word] ?? 0) + 1;

                    while ($currentCount[$word] > $wordCountMap[$word]) {
                        $leftWord = substr($s, $left, $wordLength);
                        $currentCount[$leftWord]--;
                        $left += $wordLength;
                    }

                    if ($right - $left === $totalLength) {
                        $result[] = $left;
                    }
                } else {
                    $currentCount = [];
                    $left = $right;
                }
            }
        }

        sort($result);
        return $result;
    }
}