Задача: 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:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ns, np = len(s), len(p)
        if ns < np:
            return []

        pCount = Counter(p)
        sCount = Counter()

        output = []
        for i in range(ns):
            sCount[s[i]] += 1

            if i >= np:
                if sCount[s[i - np]] == 1:
                    del sCount[s[i - np]]
                else:
                    sCount[s[i - np]] -= 1

            if pCount == sCount:
                output.append(i - np + 1)

        return output

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