30. Substring with Concatenation of All Words

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        var size = words[0].Length;
        var window = size * words.Length;
        var wordMap = new Dictionary<string, int[]>();
        foreach (var word in words)
        {
            if (!wordMap.TryGetValue(word, out var map))
            {
                wordMap.Add(word, map = new int[2]);
            }
            map[0] += 1;
        }
        var checkMap = new List<(int index, string word)>();
        for (var i = 0; i <= s.Length - size; i++)
        {
            var word = s[i..(i + size)];
            if (wordMap.ContainsKey(word))
            {
                checkMap.Add((i, word));
            }
        }
        var result = new List<int>();
        var left = 0;
        while (left < checkMap.Count - words.Length)
        {
            var checkWindow = checkMap[left].index + window - size;
            var right = left;
            var prevIndex = -size;
            while (right < checkMap.Count && checkWindow >= checkMap[right].index)
            {
                if (checkMap[right].index >= prevIndex + size)
                {
                    wordMap[checkMap[right].word][1] += 1;
                    prevIndex = checkMap[right].index;
                }
                right++;
            }
            var found = true;
            foreach(var map in wordMap)
            {
                found &= map.Value[0] == map.Value[1];
                map.Value[1] = 0;
            }
            if (found)
            {
                result.Add(checkMap[left].index);
            }
            left++;
        }
        return result;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> FindSubstring(string s, vector<string> words) {
        var size = words[0].size();
        var window = size * words.size();
        var wordMap = new unordered_map<string, int[]>();
        foreach (var word in words)
        {
            if (!wordMap.TryGetValue(word, out var map))
            {
                wordMap.push_back(word, map = new int[2]);
            }
            map[0] += 1;
        }
        var checkMap = new List<(int index, string word)>();
        for (var i = 0; i <= s.size() - size; i++)
        {
            var word = s[i..(i + size)];
            if (wordMap.count(word))
            {
                checkMap.push_back((i, word));
            }
        }
        var result = new List<int>();
        var left = 0;
        while (left < checkMap.size() - words.size())
        {
            var checkWindow = checkMap[left].index + window - size;
            var right = left;
            var prevIndex = -size;
            while (right < checkMap.size() && checkWindow >= checkMap[right].index)
            {
                if (checkMap[right].index >= prevIndex + size)
                {
                    wordMap[checkMap[right].word][1] += 1;
                    prevIndex = checkMap[right].index;
                }
                right++;
            }
            var found = true;
            foreach(var map in wordMap)
            {
                found &= map.Value[0] == map.Value[1];
                map.Value[1] = 0;
            }
            if (found)
            {
                result.push_back(checkMap[left].index);
            }
            left++;
        }
        return result;
    }
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> mapOfWords = new HashMap<>();
        for (String word : words) mapOfWords.put(word, mapOfWords.getOrDefault(word, 0) + 1);

        int k = words[0].length();
        int n = words.length * k;
        int sLen = s.length();
        if (sLen < n) return answer;

        int[] arr = new int[26];
        for (String word : words) {
            for (int i = 0; i < k; i++) {
                arr[word.charAt(i) - 'a']++;
            }
        }

        int start = 0, end = n - 1;
        for (int i = 0; i <= end; i++) arr[s.charAt(i) - 'a']--;

        while (end < s.length() - 1) {
            if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
                answer.add(start);
            }
            arr[s.charAt(start++) - 'a']++;
            arr[s.charAt(++end) - 'a']--;
        }

        if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
            answer.add(start);
        }

        return answer;
    }

    public boolean allZeros(int[] arr) {
        return Arrays.stream(arr).allMatch(i -> i == 0);
    }

    public boolean validWords(String s, HashMap<String, Integer> mapOfWords, int k) {
        for (int i = 0; i * k < s.length(); i++) {
            String current = s.substring(i * k, (i + 1) * k);
            if (!mapOfWords.containsKey(current) || mapOfWords.get(current) == 0) return false;
            mapOfWords.put(current, mapOfWords.get(current) - 1);
        }
        return true;
    }
}

var findSubstring = function(s, words) {
    let len = words[0].length;    let windowSize = words.length * len;
    if (s.length < windowSize) {        return [];
    }    let m = new Map(), res = [];
    // Fill Hash table with entry being (word, number of occurrences)    for (let i = 0; i < words.length; i++) {
        m.set(words[i], m.get(words[i]) + 1  1);    }
    let start = 0;    while (start + windowSize - 1 < s.length) {
        if (isConcat(s, new Map(m), len, start, start + windowSize-1)) {            res.push(start);
        }        start++;
    }    return res;
    // Let M be the length of s, N be the number of words    // T.C: O(M*N)
    // S.C: O(M*N), new map is used for every iteration};
const isConcat = (s, m, len, start, end) => {
    let chars = m.size;    for (let i = start; i <= end; i += len) {
        let substr = s.substring(i, i+len);        if (!m.has(substr)  m.get(substr) === 0) return false;
        m.set(substr, m.get(substr) - 1);        if (m.get(substr) === 0) {
            chars--;        }
    }    return chars === 0;
    // if we consider time complexity of substring() to be O(1),    // T.C: O(N)
}

from collections import defaultdict 
 
class Solution: 
    def findSubstring(self, s: str, words: List[str]) -> List[int]: 
        if not s or not words: 
            return [] 
         
        word_count = defaultdict(int) 
        for word in words: 
            word_count[word] += 1 
         
        substr_len = len(words) * len(words[0]) 
        word_len = len(words[0]) 
        result = [] 
         
        for i in range(len(s) - substr_len + 1): 
            seen = defaultdict(int) 
            for j in range(i, i + substr_len, word_len): 
                word = s[j:j+word_len] 
                if word in word_count: 
                    seen[word] += 1 
                    if seen[word] > word_count[word]: 
                        break 
                else: 
                    break 
            else: 
                result.append(i) 
         
        return result

import "sort"

func findSubstring(s string, words []string) []int {
    sort.Strings(words)
    var result []int
    for i := range s {
        if startsWithConcatenatedSubstring(s[i:], words) {
            result = append(result, i)
        }
    }
    return result
}

func startsWithConcatenatedSubstring(s string, words []string) bool {
    var parts[] string
    wl := len(words[0])
    for i := range words {
        startPos := wl*i
        endPos := wl*(i+1)
        if endPos > len(s) {
            return false
        }
        p := s[startPos:endPos]
        parts = append(parts, p)
    }
    sort.Strings(parts)
    for i, p := range parts {
        if p != words[i] {
            return false
        }
    }
    return true
}

Данный код представляет собой класс `Solution`, в котором содержится метод `FindSubstring`, предназначенный для поиска подстрок в строке `s`, которые являются конкатенацией всех слов из массива `words`. Вот пояснение к данному методу:

1. В начале метода инициализируются переменные `size` и `window`. Переменная `size` содержит длину одного слова из массива `words`, а переменная `window` - общую длину всех слов из массива `words`.

2. Создается словарь `wordMap`, где ключом является слово из массива `words`, а значением - массив из двух элементов. Первый элемент массива используется для подсчета количества вхождений данного слова в массив `words` (значение `0` увеличивается на `1` при каждом добавлении слова).

3. Затем создается список `checkMap`, который содержит кортежи с индексом и самим словом из строки `s`, если это слово содержится в `wordMap`.

4. В цикле `while` осуществляется проверка каждого слова в `checkMap` и заполняется словарь `wordMap` вторыми значениями, показывающими количество соответствующих слов в текущем окне.

5. Затем происходит проверка, все ли слова из массива `words` содержатся в текущем окне. Если все слова содержатся, их вторые значения обнуляются и индекс начала окна добавляется в результат `result`.

6. Метод возвращает список индексов начала подстрок, где все слова массива `words` содержатся в строке `s` в нужной последовательности.

Данный метод реализует алгоритм поиска подстроки, составленной из всех слов массива, в заданной строке.