Substring of Concatenated Word Permutations

hard string sliding window hash map

Problem

Given a string s and a list of equal-length words, return every starting index where some permutation of the words appears as a substring back-to-back. Since every word has the same length L, you can step the window in chunks of L instead of one character at a time. For each of the L possible alignment offsets, slide a window across word slots and keep a multiset of "words seen" matching the multiset of "words needed."

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;
}

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