---
title: Find All Anagrams in a String
difficulty: Medium
category: Hash Table
leetcode_id: 438
revision_count: 1
last_revision: 2026-09-12
---

# Find All Anagrams in a String

> **LeetCode:** [#438](https://leetcode.com/problems/find-all-anagrams-in-a-string/)
> **Сложность:** Medium
> **Категория:** Hash Table

## Условие

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

```
Input:  s = "cbaebabacd", p = "abc"  →  Output: [0, 6]
Input:  s = "abab",       p = "ab"   →  Output: [0, 1, 2]
Input:  s = "a",          p = "ab"   →  Output: []
```

## Ключевая идея

Скользящее окно фиксированной длины = `p.length` с частотным счётчиком символов. Сравниваем частотную карту окна с эталонной картой `p`. Чтобы не пересчитывать окно с нуля, обновляем счётчик инкрементально: добавляем правый символ, убираем левый.

## Оценка сложности

- **Время:** O(n × 26) = O(n), где n = `s.length` — один проход с покомпонентным сравнением массивов из 26 элементов на каждом шаге
- **Память:** O(1) — два массива фиксированного размера 26

## Решение (Ruby)

```ruby
# @param {String} s
# @param {String} p
# @return {Integer[]}
def find_anagrams(s, p)
  return [] if s.length < p.length

  p_count = Array.new(26, 0)
  s_count = Array.new(26, 0)
  result = []

  p.each_byte { |b| p_count[b - 97] += 1 }

  # заполняем первое окно
  p.length.times { |i| s_count[s[i].ord - 97] += 1 }

  result << 0 if s_count == p_count

  # скользим: добавляем правый, убираем левый
  (p.length...s.length).each do |i|
    s_count[s[i].ord - 97] += 1
    s_count[s[i - p.length].ord - 97] -= 1
    result << i - p.length + 1 if s_count == p_count
  end

  result
end
```

## Разбор на примере

```
s = "cbaebabacd", p = "abc", len(p) = 3

p_count = [1,1,1,0,0,...]  (a=1, b=1, c=1)

Шаг 0 (окно [0..2] = "cba"): s_count = [1,1,1,0,...] == p_count → result << 0
Шаг 1 (окно [1..3] = "bae"):
  +s[3]='e'(101): s_count[4] += 1 → [1,1,1,0,1,...]
  -s[0]='c'(99):  s_count[2] -= 1 → [1,1,0,0,1,...]
  != p_count
Шаг 2 (окно [2..4] = "aeb"):
  +s[4]='b'(98):  s_count[1] += 1 → [1,2,0,0,1,...]
  -s[1]='b'(98):  s_count[1] -= 1 → [1,1,0,0,1,...]
  != p_count
Шаг 3 (окно [3..5] = "eba"):
  +s[5]='a'(97):  s_count[0] += 1 → [2,1,0,0,1,...]
  -s[2]='e'(101): s_count[4] -= 1 → [2,1,0,0,0,...]
  != p_count
Шаг 4 (окно [4..6] = "bab"):
  +s[6]='b'(98):  s_count[1] += 1 → [2,2,0,0,0,...]
  -s[3]='e'(101): s_count[4] -= 1 → [2,2,0,0,0,...]
  != p_count
Шаг 5 (окно [5..7] = "aba"):
  +s[7]='b'(98):  s_count[1] += 1 → [2,3,0,0,0,...]
  -s[4]='b'(98):  s_count[1] -= 1 → [2,2,0,0,0,...]
  != p_count
Шаг 6 (окно [6..8] = "bac"):
  +s[8]='c'(99):  s_count[2] += 1 → [2,2,1,0,0,...]
  -s[5]='a'(97):  s_count[0] -= 1 → [1,2,1,0,0,...]
  == p_count → result << 6

Result: [0, 6]
```

## Edge Cases

- **s.length < p.length**: `[]` — окно не помещается, ни одной анаграммы нет.
- **s == p**: `[0]` — вся строка — единственная анаграмма.
- **Все символы одинаковые**: `s = "aaaa", p = "aa"` → `[0, 1, 2]` — каждое окно подходит.
- **Нет ни одной анаграммы**: `[]`.
- **Пустая s или p**: если `p` — пустая, условие не определено; возвращаем `[]`. Если `s` пустая — `[]`.

## Типичные ошибки

1. ❌ **Не проверять длину заранее**: если `s` короче `p`, sliding window выдаёт ошибки или лишние проходы.
2. ❌ **Пересчитывать каждое окно с нуля**: O(n × p.length) — для длинной `s` и большого `p` это квадрат.
3. ❌ **Забыть убрать левый символ при сдвиге**: дельта-счётчик будет накапливать старые символы.
4. ❌ **Использовать `slice` окна и сортировать**: O(n × p log p) — пройдёт, но плохо.
5. ❌ **Indices off-by-one**: индекс для `result` при записи = `i - p.length + 1`, а не `i`.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (каждую подстроку сортировать и сравнить) | O(n × p log p) | O(p) | Работает, но квадратично |
| Sliding window + Hash Map (универсальный, любые символы) | O(n) | O(k) | Для Unicode/мультибайта — вместо Array[26] используем Hash |
| **Sliding window + Array[26] (lowercase)** | **O(n × 26)** | **O(1)** | **финальное решение** — быстрее хэша за счёт прямой адресации |
| Sliding window + diff counter (оптимизация сравнения) | O(n) | O(1) | Вместо `s_count == p_count` на каждом шаге — считаем `matches`, обновляем при дельте. Ускоряет только в теории — Ruby array compare кэшируется на уровне Си |

Детали оптимизации с diff counter:
- Считаем количество совпадающих частот (`matches = 26`, если все равны).
- При добавлении/удалении символа обновляем только его счётчик и, если после изменения он сравнялся с `p_count` или разошёлся, корректируем `matches`.
- Сравнение массивов через `==` на Ruby даёт O(26) покомпонентно, но на практике это нативная Си-функция — разница заметна только на очень больших `n`.

## Заметки после повторения

_— Заполняется после каждой тренировки._