28. Substring with Concatenation of All Words

Every word has the same length L, so a valid substring is a sequence of whole L-length chunks. Run a sliding window in chunk steps for each of the L possible starting offsets, keeping a running count of how many needed words are currently matched.

Idea

All words share one length L, so any concatenated substring lines up on an L-character grid. There are only L distinct alignments (offsets 0..L-1); within each, we slide a window forward one word at a time and never re-scan characters.

Maintain a need count (how many of each word we require) and a window count of what's currently inside. When a chunk is a needed word, add it and — if we now have too many copies — shrink from the left until valid. Whenever the window holds exactly wcount words, its left edge is a match. A chunk that isn't a needed word resets the window.

Algorithm

For each offset in 0..L-1, walk right in steps of L:

1. Read the chunk word = s[right:right+L].
2. If word is needed: increment window[word] and count; while window[word] > need[word], drop the leftmost chunk (advance left). If count == wcount, record left, then drop one from the left to keep sliding.
3. If word is not needed: clear the window, reset count, jump left past this chunk.

Worked example: s = "barfoothefoobarman", words = ["foo","bar"] (L=3)

• Offset 0: bar(✓)foo(✓) → count 2 → record index 0; then the resets. Later foo+bar at index 9 → record 9.

Result: [0, 9].

Complexity

• Time: O(L · n/L) = O(n) amortized — each chunk enters/leaves a window once per offset.
• Space: O(words) for the two counts.

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

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.isEmpty() || words.length == 0) {
            return result;
        }
        int wlen = words[0].length();
        int wcount = words.length;
        int total = wlen * wcount;
        if (total > s.length()) {
            return result;
        }
        Map<String, Integer> need = new HashMap<>();
        for (String w : words) {
            need.merge(w, 1, Integer::sum);
        }
        for (int offset = 0; offset < wlen; offset++) {
            int left = offset, count = 0;
            Map<String, Integer> window = new HashMap<>();
            int right = offset;
            while (right + wlen <= s.length()) {
                String word = s.substring(right, right + wlen);
                right += wlen;
                if (need.containsKey(word)) {
                    window.merge(word, 1, Integer::sum);
                    count++;
                    while (window.get(word) > need.get(word)) {
                        String lw = s.substring(left, left + wlen);
                        window.merge(lw, -1, Integer::sum);
                        left += wlen;
                        count--;
                    }
                    if (count == wcount) {
                        result.add(left);
                        String lw = s.substring(left, left + wlen);
                        window.merge(lw, -1, Integer::sum);
                        left += wlen;
                        count--;
                    }
                } else {
                    window.clear();
                    count = 0;
                    left = right;
                }
            }
        }
        Collections.sort(result);
        return result;
    }
}