Задача: 30. Substring with Concatenation of All Words
Сложность: hard

Дана строка s и массив строк words, где все слова одинаковой длины.
Нужно вернуть все начальные индексы подстрок в s, которые являются конкатенацией всех слов из массива words в любой перестановке.
Слова не могут быть разделены, повторения допустимы.

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]

👨‍💻 Алгоритм:

1️⃣ Вычисляем:
- len — длина одного слова
- windowSize — общее число символов в одной перестановке всех слов
- Если s.length < windowSize, возвращаем []

2️⃣ Заполняем Map m, где ключ — слово из words, значение — количество его вхождений

3️⃣ Двигаемся по строке s посимвольно:
- Для каждого индекса start проверяем, является ли подстрока от start длины windowSize валидной комбинацией слов из m
- Для проверки используем isConcat()

😎 Решение:

var findSubstring = function(s, words) {
    const len = words[0].length;
    const windowSize = words.length * len;
    if (s.length < windowSize) return [];

    const m = new Map();
    const res = [];

    for (let word of words) {
        m.set(word, (m.get(word) || 0) + 1);
    }

    for (let start = 0; start <= s.length - windowSize; start++) {
        if (isConcat(s, new Map(m), len, start, start + windowSize - 1)) {
            res.push(start);
        }
    }

    return res;
};

function isConcat(s, m, len, start, end) {
    let chars = m.size;
    for (let i = start; i <= end; i += len) {
        const word = s.substring(i, i + len);
        if (!m.has(word) || m.get(word) === 0) return false;
        m.set(word, m.get(word) - 1);
        if (m.get(word) === 0) chars--;
    }
    return chars === 0;
}

Ставь 👍 и забирай 📚 Базу знаний