---
round: 3
ticket_no: 15
source_no: 6
slug: permutation-in-string
topic: Hash Table
difficulty: Medium
leetcode_id: 567
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 15 — Permutation in String

## Условие (как предъявлено)

Даны две строки `s1` и `s2`. Верните `true`, если `s2` содержит перестановку `s1`.

```
Input:  s1 = "ab", s2 = "eidbaooo"  →  Output: true
Input:  s1 = "ab", s2 = "eidboaoo"  →  Output: false
```

Constraints: `1 <= s1.length, s2.length <= 10^4`; строки состоят из строчных английских букв.

## Ответ

> Значит, здесь мы двигаемся тоже окном. Окном является длина меньшего из этих строк, то есть с1. Значит, пока мы по окну двигаемся, мы накапливаем хэш со счетчиками каждого символа, который там присутствует. И у нас должен быть один раз сделан хэш счетчиков символов с1. Дальше мы сравниваем их: если они совпали, всё, мы выходим, возвращаем, что у нас найдено. Когда окно сдвигается, мы, получается, выпавший элемент вычитаем. Счетчик, их может быть несколько, этот он раз встречался, да, поэтому там счетчик уменьшается или прибавляется — прибавляется как до элемент, который мы добавляем, и мы вот так доходим до конца.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/01-must-have/02-hash-table/06-permutation-in-string.md`](../../algo-solutions/01-must-have/02-hash-table/06-permutation-in-string.md)