---
round: 1
ticket_no: 23
source_no: 2
slug: partition-labels
topic: Two Pointers
difficulty: Medium
leetcode_id: 763
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 23 — Partition Labels

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

Дана строка `s`. Нужно разбить её на максимально возможное число частей так, чтобы каждая буква встречалась только в одной части. Вернуть список длин этих частей в порядке слева направо.

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

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

## Ответ

> Так что если первым проходом мы составим для каждого, ну, составим хэш, вот для каждой буквы мы будем знать первый индекс, где он встречается, и последний индекс, где он встречается. Этот именно символ, эта буква. Так, предположим, при первом проходе мы это получили. Теперь вот мы получили, теперь второй проход мы начинаем формулировать наши вот эти интервалы. Мы проходимся, а значит, у него максимальный элемент сейчас там пример там 1, 1, 2, 3. То есть мы знаем, что у нее последний элемент, там, не знаю, восьмой какой-нибудь, да. Дальше мы переходим ко второму элементу. То есть, вот у нас вот этот диапазон появился. Дальше мы Б проверяем. Мы его встретили. Дальше ищем, а где максимальный у него элемент? То есть он расширяет наш диапазон или нет? Если расширяет, то мы, значит, идём дальше. То есть мы сейчас до конца этого диапазона будем идти. Дальше встретили С, смотрим, какой у него последний элемент. Он внутри диапазона. То есть мы доходим до конца нашего диапазона. Он больше не расширяется. Всё, мы его размер теперь знаем. Записали в результат. Теперь начинаем снова новый диапазон. Берём первый элемент, смотрим по нашему хэшу, где у него последний. Вот и значит, это наш кандидат на завершение, и также проходимся до конца.

## Разбор

**Что верно:** первый проход — последние вхождения букв, второй — расширение границы части до максимума last среди встреченных символов, закрытие при i == end, запись длины и старт новой части — точный эталон.

**Что упущено и ошибки:** достаточно только last occurrence (first не нужен) — это не ошибка, но лишняя сущность; не названа сложность O(n) / O(1); граничные случаи (одна буква, все буквы разные, все одинаковые).

**Эталонная идея:** last = {}; s.each_char.with_index { |c, i| last[c] = i }; затем один проход: end = [end, last[c]].max, при i == end записать end - start + 1 и start = i + 1.

**Сложность:** время O(n), память O(1) (алфавит константный)

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


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