30. Substring with Concatenation of All Words

Hash Table
String
Sliding Window

TIME

O(n * L)

SPACE

O(m * L)

Intuition

Every word has the same length L, which makes the problem far more structured than a general permutation search: a valid window is always exactly L * m characters long (m = len(words)), and it must start at an index whose position mod L stays fixed throughout the window. So the string splits into L independent "tracks", one per starting offset, and within a track the text is just a sequence of L-sized blocks.

That lets a sliding window advance a whole word at a time instead of a character at a time, and lets the window state be a simple count map compared against the required counts (duplicates in words matter, which is why counts are used rather than a set).

Three situations arise as the right edge takes in a new word:

Unknown word, no valid window can span it, so drop everything and restart just past it.
Known but now over-counted, shrink from the left, one word at a time, until the excess is gone.
Window complete (m words), record the start index, then slide the left edge forward by one word to look for the next match.

Approach

Let L = len(words[0]), m = len(words), and build need = a count map of words. If L * m > len(s), return [].
For each offset in 0 .. L-1:
- Set left = offset, count = 0, and an empty window count map.
- For right stepping from offset by L:
  - Take word = s[right : right + L].
  - If word is not in need: clear window, set count = 0, left = right + L.
  - Else: increment window[word] and count; while window[word] > need[word], remove the word at left and advance left by L; then if count == m, append left to the results and slide the left edge one word forward.
Return the collected indices.

Complexity

Time: O(n * L), across all offsets there are O(n / L) * L = O(n) window steps, each extracting/hashing an L-character substring
Space: O(m * L), the two count maps

Edge Cases

L * m > len(s) → no window can fit → []
Duplicate words (Example 2's two "word"s) → counts, not sets, are required
Overlapping answers (Example 3 returns 6, 9, 12) → sliding by one word after a hit finds them
An unknown word must reset the window entirely, not merely shrink it
Single word in words → degenerates to finding all occurrences of that word

Code

from typing import List
from collections import Counter, defaultdict


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        """
        30. Substring with Concatenation of All Words
        Time: O(n * L)
        Space: O(m * L)
        """
        n = len(s)
        L = len(words[0])
        m = len(words)
        total = L * m
        if total > n:
            return []

        need = Counter(words)
        result = []

        # Windows only align to L distinct offsets; scan each track separately.
        for offset in range(L):
            window = defaultdict(int)
            left = offset
            count = 0

            for right in range(offset, n - L + 1, L):
                word = s[right:right + L]

                if word not in need:
                    # No valid window can span an unknown word: restart past it.
                    window.clear()
                    count = 0
                    left = right + L
                    continue

                window[word] += 1
                count += 1

                # Too many copies of this word: shrink from the left.
                while window[word] > need[word]:
                    window[s[left:left + L]] -= 1
                    left += L
                    count -= 1

                if count == m:
                    result.append(left)
                    # Slide one word forward to look for the next match.
                    window[s[left:left + L]] -= 1
                    left += L
                    count -= 1

        return result

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 30. Substring with Concatenation of All Words
 * Time: O(n * L)
 * Space: O(m * L)
 */
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int n = s.length();
        int L = words[0].length();
        int m = words.length;
        if ((long) L * m > n) {
            return result;
        }

        Map<String, Integer> need = new HashMap<>();
        for (String w : words) {
            need.merge(w, 1, Integer::sum);
        }

        // Windows only align to L distinct offsets; scan each track separately.
        for (int offset = 0; offset < L; offset++) {
            Map<String, Integer> window = new HashMap<>();
            int left = offset;
            int count = 0;

            for (int right = offset; right + L <= n; right += L) {
                String word = s.substring(right, right + L);

                if (!need.containsKey(word)) {
                    // No valid window can span an unknown word: restart past it.
                    window.clear();
                    count = 0;
                    left = right + L;
                    continue;
                }

                window.merge(word, 1, Integer::sum);
                count++;

                // Too many copies of this word: shrink from the left.
                while (window.get(word) > need.get(word)) {
                    String lw = s.substring(left, left + L);
                    window.merge(lw, -1, Integer::sum);
                    left += L;
                    count--;
                }

                if (count == m) {
                    result.add(left);
                    // Slide one word forward to look for the next match.
                    String lw = s.substring(left, left + L);
                    window.merge(lw, -1, Integer::sum);
                    left += L;
                    count--;
                }
            }
        }

        return result;
    }
}