438. Find All Anagrams in a String — разбор задачи

1. Условие задачи

Дано: две строки s и p, состоящие из строчных английских букв.

Нужно: найти все индексы, с которых в строке s начинаются анаграммы строки p.

Анаграмма содержит те же буквы и в тех же количествах, но их порядок может отличаться. Например, строки abc, bca и cab — анаграммы друг друга.

Рассмотрим пример:

s = "cbaebabacd"
p = "abc"

Подстрока cba начинается с индекса 0, а подстрока bac — с индекса 6. Обе содержат по одной букве a, b и c, поэтому ответ:

[0, 6]

Ограничения:

длины s и p — от 1 до 3 * 10^4;
строки содержат только строчные английские буквы;
если p длиннее s, ответ будет пустым.

2. Решение

Решение в лоб

Можно перебрать каждую подстроку s длины len(p), заново посчитать в ней буквы и сравнить результат с частотами букв в p.

Таких подстрок до N, а обработка каждой занимает O(K), где K = len(p). Получаем O(N * K): мы много раз пересчитываем почти одно и то же.

Первое решение: скользящее окно и `Counter`

Любая анаграмма p имеет ту же длину, что и p. Значит, по строке s можно двигать скользящее окно фиксированной длины K.

При сдвиге окна на один символ почти ничего не меняется:

один символ входит в окно справа;
один символ выходит из окна слева.

Поэтому вместо полного пересчёта достаточно обновить частоты только этих двух символов.

В Python частоты удобно хранить в Counter — специальном словаре, где ключом является символ, а значением — число его появлений.

Создадим два счётчика:

cnt_p — частоты букв в строке p;
cnt_cur — частоты букв в текущем окне строки s.

Если счётчики равны, окно содержит ровно те же буквы в тех же количествах, что и p. Значит, перед нами анаграмма.

При каждом сдвиге добавляем в cnt_cur новый символ справа и вычитаем старый символ слева. Если частота старого символа стала равна нулю, удаляем его из Counter, чтобы внутри не оставались ненужные нулевые ключи.

Именно решение через скользящее окно и две хеш-таблицы первым приводит официальный editorial:

https://leetcode.com/problems/find-all-anagrams-in-a-string/editorial/

Алгоритм через `Counter`

Если p длиннее s, сразу возвращаем пустой список.
Считаем буквы строки p в cnt_p, а cnt_cur оставляем пустым.
Двигаем правую границу r по строке s и добавляем очередной символ в cnt_cur.
Если окно стало длиннее p, удаляем из него символ слева.
Сравниваем cnt_cur с cnt_p.
Если два счётчика равны, добавляем индекс начала окна в ответ.

Код на Python: решение через `Counter`

from collections import Counter
from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        cnt_p = Counter(p)
        cnt_cur = Counter()

        ans = []
        l = 0

        for r, ch in enumerate(s):
            cnt_cur[ch] += 1

            if r - l + 1 > len(p):
                left_ch = s[l]
                cnt_cur[left_ch] -= 1

                # В современных версиях Python в целом не обязательно
                if cnt_cur[left_ch] == 0:
                    del cnt_cur[left_ch]

                l += 1

            if cnt_cur == cnt_p:
                ans.append(l)

        return ans

Это решение уже быстрое и хорошо читается: мы не пересчитываем каждое окно с нуля, а обновляем готовый словарь всего двумя символами.

Но сравнение cnt_cur == cnt_p всё равно просматривает ключи двух счётчиков. В этой задаче ключей не больше 26, поэтому асимптотически это константа. Однако можно пойти дальше и вообще отказаться от сравнения словарей на каждом шаге.

Продвинутое решение: один массив и `missing`

Будем хранить массив cnt из 26 элементов. Изначально cnt[index] показывает, сколько экземпляров этой буквы нам нужно взять из s, чтобы собрать p.

Также заведём переменную missing — сколько символов из p нам ещё не хватает. Изначально missing = len(p).

Когда в окно входит символ:

если его ещё не хватало (cnt[index] > 0), уменьшаем missing;
в любом случае уменьшаем cnt[index].

Значение cnt[index] может стать отрицательным. Это не ошибка: отрицательное число означает, что в окне есть лишние экземпляры этой буквы.

Когда символ выходит из окна, выполняем обратные действия:

увеличиваем его счётчик;
если после этого cnt[index] > 0, значит, мы выбросили нужный символ и снова должны увеличить missing.

Если окно имеет длину len(p) и missing == 0, в нём есть все необходимые символы. Поскольку длины окна и p совпадают, лишних символов там быть уже не может — перед нами анаграмма.

В популярных пользовательских решениях встречается более общий шаблон с отдельным счётчиком совпадений. Он позволяет не сравнивать все частоты на каждом шаге:

https://leetcode.com/problems/find-all-anagrams-in-a-string/solutions/

Алгоритм через `count` и `missing`

Если p длиннее s, сразу возвращаем пустой список.
Создаём массив cnt длины 26 и записываем в него частоты букв строки p.
Кладём в missing длину p, а левую границу окна l ставим в 0.
Двигаем правую границу r по строке s и учитываем входящий символ.
Если r - l + 1 > len(p), удаляем из окна символ s[l] и увеличиваем l.
Если missing == 0, добавляем l в ответ.

Визуализация на `s = "cbaebabacd"`, `p = "abc"`

В начале нам не хватает трёх символов:

cnt: a=1, b=1, c=1
missing = 3

Строка `s` (окно выделено)	Вошёл	Вышел	missing	Результат
`[c]baebabacd`	`c`	—	2	окно ещё короткое
`[cb]aebabacd`	`b`	—	1	окно ещё короткое
`[cba]ebabacd`	`a`	—	0	анаграмма, добавляем `0`
`c[bae]babacd`	`e`	`c`	1	не хватает `c`
`cb[aeb]abacd`	`b`	`b`	1	не хватает `c`
`cba[eba]bacd`	`a`	`a`	1	не хватает `c`
`cbae[bab]acd`	`b`	`e`	1	не хватает `c`, одна `b` лишняя
`cbaeb[aba]cd`	`a`	`b`	1	не хватает `c`, одна `a` лишняя
`cbaeba[bac]d`	`c`	`a`	0	анаграмма, добавляем `6`
`cbaebab[acd]`	`d`	`b`	1	не хватает `b`

Ответ: [0, 6].

Код на Python: продвинутое решение

from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        cnt = [0] * 26
        for ch in p:
            cnt[ord(ch) - ord("a")] += 1

        ans = []
        l = 0
        missing = len(p)

        for r, ch in enumerate(s):
            right_index = ord(ch) - ord("a")

            if cnt[right_index] > 0:
                missing -= 1
            cnt[right_index] -= 1

            if r - l + 1 > len(p):
                left_index = ord(s[l]) - ord("a")
                cnt[left_index] += 1

                if cnt[left_index] > 0:
                    missing += 1

                l += 1

            if missing == 0:
                ans.append(l)

        return ans

Почему алгоритм работает

Массив cnt хранит разницу между тем, сколько экземпляров каждой буквы требуется строке p, и тем, сколько находится в текущем окне.

Переменная missing равна общему числу ещё не найденных символов p. Мы уменьшаем её только тогда, когда входящий символ закрывает реальную нехватку, и увеличиваем только тогда, когда из окна выходит реально нужный символ. Поэтому missing == 0 означает, что окно содержит все символы p с нужными частотами.

Мы поддерживаем длину окна не больше len(p). Когда эта длина равна len(p), наличие всех нужных символов автоматически означает отсутствие лишних: для них просто не осталось места. Следовательно, каждое добавленное в ответ окно является анаграммой p.

И наоборот, если окно является анаграммой, оно содержит все символы p в нужных количествах. Значит, missing обязательно равно нулю, и его левую границу мы добавим в ответ.

Краевые случаи

p длиннее s. Окно нужного размера не поместится в строку, поэтому сразу возвращаем [].
Строки одинаковой длины. Проверим единственное возможное окно и вернём либо [0], либо [].
Все символы одинаковые. Например, s = "aaaa", p = "aa": окна могут пересекаться, поэтому получим [0, 1, 2].
Анаграммы пересекаются. Мы сдвигаем окно на один символ, а не на его полную длину, поэтому не пропускаем пересекающиеся ответы.
В окне есть лишняя буква. Её значение в count становится отрицательным, а missing не уменьшается.
В p есть повторяющиеся буквы. Частоты учитывают каждый экземпляр отдельно.

3. Сложность алгоритма

Обозначим через N длину строки s, а через K — длину строки p.

Решение через `Counter`

Построение Counter(p) занимает O(K).
Затем окно сдвигается по строке за O(N).
Сравнение двух Counter занимает до O(A), где A — размер алфавита.
Для строчных английских букв A <= 26, поэтому он считается константой.
В двух счётчиках хранится не больше 26 ключей.

Итог по времени: O(N * A + K), или O(N + K) при фиксированном алфавите из 26 букв.

Итог по памяти: O(A), или O(1) при фиксированном алфавите.

Продвинутое решение

Подсчёт букв в p занимает O(K).
Правая граница проходит по s один раз: O(N).
Левая граница тоже только движется вперёд; каждый символ входит в окно и выходит из него не более одного раза.
Все обновления массива cnt и переменной missing занимают O(1).
Массив частот всегда содержит ровно 26 элементов: O(1) дополнительной памяти.

Итог по времени: O(N + K) без сравнения частотных структур на каждом шаге.

Итог по памяти: O(1) дополнительной памяти, если не считать массив с ответом.

Главная идея задачи: если мы ищем в строке перестановки шаблона, порядок букв не важен — важны только их частоты. А когда все кандидаты имеют одну длину, эти частоты удобно поддерживать скользящим окном: добавили символ справа, убрали символ слева и не пересчитываем всё заново.

🐆

1. Условие задачи

2. Решение

Решение в лоб

Первое решение: скользящее окно и Counter

Алгоритм через Counter

Код на Python: решение через Counter

Продвинутое решение: один массив и missing

Алгоритм через count и missing

Визуализация на s = "cbaebabacd", p = "abc"