Задача: 438. Find All Anagrams in a String
Сложность: medium

Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.

Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

class Solution {
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        let ns = s.count, np = p.count
        if ns < np { return [] }

        var pCount = [Character: Int]()
        var sCount = [Character: Int]()

        for ch in p {
            pCount[ch, default: 0] += 1
        }

        var output = [Int]()

        let sArray = Array(s)
        for i in 0..<ns {
            let ch = sArray[i]
            sCount[ch, default: 0] += 1

            if i >= np {
                let leftChar = sArray[i - np]
                if sCount[leftChar] == 1 {
                    sCount.removeValue(forKey: leftChar)
                } else {
                    sCount[leftChar]! -= 1
                }
            }

            if pCount == sCount {
                output.append(i - np + 1)
            }
        }
        return output
    }
}

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