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

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

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

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

Пример:

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

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

1⃣Определяем длину слова len и количество слов cnt.

2⃣Создаем словарь wf с частотами слов в words.

3⃣Проходим по строке s, проверяя подстроки длиной cnt * len.

😎Решение:

class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        let len = words.first!.count
        let cnt = words.count

        guard s.count >= cnt * len else { return [] }
        
        let s = Array(s)
        let words = words.map(Array.init)
        let wf = words.reduce(into: [[Character]: Int]()) { $0[$1, default: 0] += 1 }
        let ws = Set(words)
        var res = [Int]()

        for i in 0...(s.count - cnt * len) {
            var sf = [[Character]: Int]()
            var j = i

            for _ in 0..<cnt {
                let w = Array(s[j..<j + len])
                guard ws.contains(w) else { break }

                let old = sf[w, default: 0]
                guard old + 1 <= wf[w]! else { break }

                sf[w] = old + 1
                j += len
            }

            guard j == i + cnt * len, sf == wf else { continue }
            res.append(i)
        }

        return res
    }
}

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