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

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

Пример:

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

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

1⃣Вычисляем длину каждого слова и общее количество слов.

2⃣Используем скользящее окно с шагом = длине слова, и на каждом шаге проверяем, входят ли текущие слова в заданный набор.

3⃣Отслеживаем, сколько раз каждое слово встречается, используя unordered_map.

😎 Решение:

vector<int> findSubstring(string str, vector<string>& words) {
    int len = words[0].length();
    unordered_map<string, int> contain;
    for (string s : words) contain[s]++;
    
    vector<int> res;
    for (int j = 0; j < len; j++) {
        unordered_map<string, int> found;
        int st = j;
        for (int i = j; i <= str.size() - len; i += len) {
            string curr = str.substr(i, len);
            if (contain.find(curr) != contain.end()) {
                found[curr]++;
                while (found[curr] > contain[curr]) {
                    found[str.substr(st, len)]--;
                    st += len;
                }
                int size = (i - st + len) / len;
                if (size == words.size()) {
                    res.push_back(st);
                }
            } else {
                found.clear();
                st = i + len;
            }
        }
    }
    return res;
}

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