Crack the Backend

Problem Statement

Given a string s and an array of equal-length words words, return all starting indices in s of substrings that are a concatenation of every word in words exactly once, in any order. No overlapping indices for the same substring; each word must appear exactly once.

All words have the same length wLen; the concatenation has length wLen * words.length. So we only need to check starting positions such that there are enough characters left.
Words can repeat in words (e.g. ["foo","bar","foo"] means we need two "foo" and one "bar").

Key Observations

We can try each possible "phase" start % wLen: for a fixed phase, we slice s into segments of length wLen starting at start, start+wLen, .... Then we slide a window over these segments and check if the window's word counts match the required counts from words.
Build a map need: word → count required. For each phase, maintain a sliding window of segments; add the segment at the right, remove from the left when the window has too many of some word. When the window exactly matches need, record the start index.
There are wLen phases and each phase is O(n/wLen) steps, so total O(n).

Approach

High-level: For each starting phase 0..wLen-1, treat s as a sequence of words of length wLen. Use a sliding window over these words; maintain a count map for the current window. When it matches the required map (from words), add the current start index to the result.

Steps:

Build need: map each word in words to its required count. wLen = words[0].length(), totalLen = wLen * words.length.
For start = 0..wLen-1: slide a window over s in steps of wLen (extract words s[start], s[start+wLen], ...). Maintain window counts; when we have exactly need, add start to result; shrink window if a word count exceeds required.
Return the list of start indices.

Implementation

Java

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int n = s.length(), wCount = words.length, wLen = words[0].length();
    Map<String, Integer> need = new HashMap<>();

    for (String w : words) {
        need.merge(w, 1, Integer::sum);
    }

    for (int start = 0; start < wLen; start++) {
        Map<String, Integer> seen = new HashMap<>();
        int count = 0;

        for (int i = start; i + wLen <= n; i += wLen) {
            String w = s.substring(i, i + wLen);

            if (need.containsKey(w)) {
                seen.merge(w, 1, Integer::sum);
                count++;

                while (seen.get(w) > need.get(w)) {
                    String remove = s.substring(start, start + wLen);
                    seen.merge(remove, -1, Integer::sum);
                    count--;
                    start += wLen;
                }

                if (count == wCount) {
                    result.add(start);
                }
            }
            else {
                seen.clear();
                count = 0;
                start = i + wLen;
            }
        }
    }

    return result;
}

Test Cases

Example 1

Input

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

Expected

[0,9]

Explanation

Substrings "barfoo" and "foobar".

Complexity Analysis

Time: O(n * wLen).
Space: O(words.length).

Follow-ups

What if words have different lengths? (Then it becomes a different problem.)