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

Вам дана строка s и массив строк-слов. Все строки-слова имеют одинаковую длину.

Объединенная строка - это строка, которая точно содержит все строки из любой перестановки слов, которые были объединены.

Например, если words = ["ab", "cd","ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются связанными строками. "acdbef" не является объединенной строкой, потому что это не объединение какой-либо перестановки слов.

Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.

Пример:

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

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

1️⃣Создаем словарь с подсчетом количества слов в words.

2️⃣Проходим по строке s, проверяя подстроки длины, равной len(words) * len(words[0]).

3️⃣Проверяем, содержит ли подстрока все слова из words в нужном количестве.

😎 Решение:

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

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