---
round: 3
ticket_no: 3
source_no: 2
slug: partition-labels
topic: Two Pointers
difficulty: Medium
leetcode_id: 763
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 03 — Partition Labels

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

Разбейте строку на максимальное число частей так, чтобы каждая буква встречалась только в одной части.

```
Input:  s = "ababcbacadefegdehijhklij"  →  Output: [9,7,8]
Input:  s = "eccbbbbdec"                 →  Output: [10]
```

Constraints: `1 <= s.length <= 500`; строка состоит из строчных английских букв.

## Ответ

> Значит, здесь мы в первый проход должны заполнить хэш, в котором ключи — это символы, а значение — это последний индекс, на котором встречается данный сим. Дальше, после того как мы это подготовили, мы начинаем наше составлять интервалы. Части. Вот мы начинаем первый интервал, он с первого числа начинается. И мы записываем: у нас есть кандидат, то есть у нас есть начало этого интервала и кандидат для завершения. Дальше он берётся из этого хэша окончания. Мы видим по этому символу, где он последний раз встречается. И дальше мы до него итерируем, бежим. По ходу дела мы проверяем каждую символ, где встречается он последний раз. Это двигаем кандидат окончания чуть дальше, если вдруг встретили больше значений. Долистали до конца этого интервала, закрыли его, положили его в результат. То есть у нас получился там вот длина интервала. Дальше открываем новый интервал и по этому же принципу действуем.

## Разбор

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

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

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

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

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

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

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

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

**Разбор задачи:** [`../../algo-solutions/01-must-have/01-two-pointers/02-partition-labels.md`](../../algo-solutions/01-must-have/01-two-pointers/02-partition-labels.md)