Substring with Concatenation of All Words

hard string sliding window hash map

Problem

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters. You can return the answer in any order.

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

Output[0, 9]

"barfoo" at 0 and "foobar" at 9 are both permutations of {foo, bar}.

words (comma-separated, equal length)

from collections import Counter

def find_substring(s, words):
    k, L = len(words), len(words[0])
    need = Counter(words)
    result = []
    for off in range(L):
        l = off
        have = Counter()
        count = 0
        r = off
        while r + L <= len(s):
            word = s[r:r + L]
            if word not in need:
                have.clear(); count = 0; l = r + L
            else:
                have[word] += 1
                count += 1
                while have[word] > need[word]:
                    drop = s[l:l + L]
                    have[drop] -= 1
                    l += L; count -= 1
                if count == k:
                    result.append(l)
            r += L
    return result

function findSubstring(s, words) {
  const k = words.length, L = words[0].length;
  const need = new Map();
  for (const w of words) need.set(w, (need.get(w) || 0) + 1);
  const result = [];
  for (let off = 0; off < L; off++) {
    let l = off, count = 0;
    const have = new Map();
    for (let r = off; r + L <= s.length; r += L) {
      const word = s.substring(r, r + L);
      if (!need.has(word)) {
        have.clear(); count = 0; l = r + L;
        continue;
      }
      have.set(word, (have.get(word) || 0) + 1);
      count++;
      while (have.get(word) > need.get(word)) {
        const drop = s.substring(l, l + L);
        have.set(drop, have.get(drop) - 1);
        l += L; count--;
      }
      if (count === k) result.push(l);
    }
  }
  return result;
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int k = words.length, L = words[0].length();
        Map<String, Integer> need = new HashMap<>();
        for (String w : words) need.merge(w, 1, Integer::sum);
        List<Integer> result = new ArrayList<>();
        for (int off = 0; off < L; off++) {
            int l = off, count = 0;
            Map<String, Integer> have = new HashMap<>();
            for (int r = off; r + L <= s.length(); r += L) {
                String word = s.substring(r, r + L);
                if (!need.containsKey(word)) {
                    have.clear(); count = 0; l = r + L;
                    continue;
                }
                have.merge(word, 1, Integer::sum);
                count++;
                while (have.get(word) > need.get(word)) {
                    String drop = s.substring(l, l + L);
                    have.merge(drop, -1, Integer::sum);
                    l += L; count--;
                }
                if (count == k) result.add(l);
            }
        }
        return result;
    }
}

vector<int> findSubstring(string s, vector<string>& words) {
    int k = words.size(), L = words[0].size();
    unordered_map<string, int> need;
    for (auto& w : words) need[w]++;
    vector<int> result;
    for (int off = 0; off < L; off++) {
        int l = off, count = 0;
        unordered_map<string, int> have;
        for (int r = off; r + L <= (int)s.size(); r += L) {
            string word = s.substr(r, L);
            if (!need.count(word)) {
                have.clear(); count = 0; l = r + L;
                continue;
            }
            have[word]++; count++;
            while (have[word] > need[word]) {
                string drop = s.substr(l, L);
                have[drop]--;
                l += L; count--;
            }
            if (count == k) result.push_back(l);
        }
    }
    return result;
}

Explanation

Every word in words has the same length L, so a valid match is just a run of k back-to-back chunks, each L letters long, that together use exactly the multiset of words. We treat each L-letter chunk as a single token and run a sliding window over tokens.

Because matches are aligned to multiples of L, there are only L possible starting offsets. We loop off from 0 to L - 1 and, for each offset, scan s in steps of L so we never re-read the same chunk boundaries.

Within one offset we keep a window of valid words in have and a running count. For each chunk word: if it is not in need, the whole window is broken, so we clear everything and restart after it. Otherwise we add it; if that makes have[word] exceed need[word], we shrink from the left, dropping words until the surplus is gone.

Whenever count == k, the window holds exactly the right words, so its start index l is a valid answer.

Example: s = "barfoothefoobarman", words = ["foo","bar"]. The chunks "bar","foo" at index 0 and "foo","bar" at index 9 both match, so the answer is [0, 9].

Time: O(n · L) Space: O(k · L)