---
title: Permutation in String
difficulty: Medium
category: Hash Table
leetcode_id: 567
revision_count: 1
last_revision: 2026-09-12
---

# Permutation in String

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

## Условие

Даны две строки `s1` и `s2`. Вернуть `true`, если `s2` содержит перестановку (анаграмму) `s1`. Иначе `false`. Перестановка должна быть непрерывной подстрокой `s2`.

```
Input:  s1 = "ab", s2 = "eidbaooo"  →  Output: true   ("ba" — перестановка "ab")
Input:  s1 = "ab", s2 = "eidboaoo"  →  Output: false
Input:  s1 = "a",  s2 = "a"         →  Output: true
Input:  s1 = "a",  s2 = "b"         →  Output: false
```

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

Скользящее окно фиксированной длины = `s1.length` с частотным счётчиком символов. Сравниваем частотную карту окна с эталонной картой `s1`. Как только совпали — `true`. Если окно дошло до конца без совпадения — `false`.

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

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

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

```ruby
# @param {String} s1
# @param {String} s2
# @return {Boolean}
def check_inclusion(s1, s2)
  return false if s1.length > s2.length

  s1_count = Array.new(26, 0)
  s2_count = Array.new(26, 0)

  s1.each_byte { |b| s1_count[b - 97] += 1 }

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

  return true if s2_count == s1_count

  # скользим: добавляем правый, убираем левый
  (s1.length...s2.length).each do |i|
    s2_count[s2[i].ord - 97] += 1
    s2_count[s2[i - s1.length].ord - 97] -= 1
    return true if s2_count == s1_count
  end

  false
end
```

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

```
s1 = "ab", s2 = "eidbaooo", len(s1) = 2

s1_count = [1,1,0,0,...]  (a=1, b=1)

Шаг 0 (окно [0..1] = "ei"):
  s2_count = [0,0,0,0,1,0,0,1,0,...]  (e=1, i=1)
  != s1_count

Шаг 1 (окно [1..2] = "id"):
  +s2[2]='d'(100): s2_count[3] += 1 → [0,0,0,1,1,0,0,1,...]
  -s2[0]='e'(101): s2_count[4] -= 1 → [0,0,0,1,0,0,0,1,...]
  != s1_count

Шаг 2 (окно [2..3] = "db"):
  +s2[3]='b'(98):  s2_count[1] += 1 → [0,1,0,1,0,0,0,1,...]
  -s2[1]='i'(105): s2_count[8] -= 1 → [0,1,0,1,0,0,0,0,...]
  != s1_count

Шаг 3 (окно [3..4] = "ba"):
  +s2[4]='a'(97):  s2_count[0] += 1 → [1,1,0,1,0,0,0,0,...]
  -s2[2]='d'(100): s2_count[3] -= 1 → [1,1,0,0,0,0,0,0,...]
  == s1_count → return true

Result: true
```

## Edge Cases

- **s1.length > s2.length**: `false` — окно не помещается.
- **s1 == s2**: `true` — вся строка — искомая перестановка.
- **Один символ в s1**: достаточно найти этот символ в s2: O(n).
- **Пустая s1**: по условию неопределено; если `s1` пустая, пустая строка — перестановка пустой строки → `true`.
- **Нет ни одной перестановки**: `false`.
- **Разные регистры / Unicode**: решение на Array[26] работает только для латинских строчных. Для полного Unicode потребуется хэш-счётчик.

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

1. ❌ **Забыть проверить длину заранее**: если `s1` длиннее `s2`, sliding window выдаёт ошибку или лишние проходы.
2. ❌ **Пересчитывать каждое окно с нуля**: O(n × s1.length) — квадратичная сложность.
3. ❌ **Забыть убрать левый символ**: счётчик накапливает старые символы, сравнение никогда не совпадёт.
4. ❌ **Не возвращать `true` раньше времени**: можно досрочно выйти при первом совпадении, не перебирая весь `s2`.
5. ❌ **Off-by-one в индексах левого символа**: `s2[i - s1.length]`, а не `s2[i - s1.length - 1]`.
6. ❌ **Сравнивать с `s1` вместо `s1_count`**: прямое сравнение строк — квадратично и бессмысленно.

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

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (все подстроки сортировать) | O(n × s1 log s1) | O(s1) | Проверяет каждую подстроку длины s1 — медленно |
| Sliding window + Hash Map (универсальный) | O(n × Σ) | O(k) | Для строк с любыми символами (Unicode) |
| **Sliding window + Array[26] (lowercase only)** | **O(n × 26)** | **O(1)** | **финальное решение** — прямая адресация быстрее хэша |
| Sliding window + diff counter (match count) | O(n) | O(1) | Считаем количество совпадающих частот, обновляем при дельте. Ещё быстрее на больших `n` |

Оптимизация с diff counter:
- Вместо `s2_count == s1_count` (O(26)) на каждом шаге считаем `matches` — количество символов, у которых частота совпадает с эталоном.
- Изначально `matches = 0`, при добавлении/удалении символа обновляем его счётчик и корректируем `matches`.
- Когда `matches == 26` — `true`.
- На Ruby разница малозаметна: `Array#==` — нативная Си-функция.

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

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