---
title: Partition Labels
difficulty: Medium
category: Two Pointers
leetcode_id: 763
revision_count: 1
last_revision: 2026-09-12
---

# Partition Labels

> **LeetCode:** [#763](https://leetcode.com/problems/partition-labels/)
> **Сложность:** Medium
> **Категория:** Two Pointers + Hash Table (Greedy)

## Условие

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

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

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

Жадный подход: **сначала** находим последнее вхождение каждого символа. Затем проходим строку, расширяя границу текущей части до максимального last-индекса среди встреченных символов. Как только дошли до этой границы — часть закончена.

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

- **Время:** O(n) — два прохода (last hash + partition scan)
- **Память:** O(1) — hash на 26 букв (константный размер алфавита)

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

```ruby
# @param {String} s
# @return {Integer[]}
def partition_labels(s)
  # 1. Последнее вхождение каждого символа
  last = {}
  s.each_char.with_index { |ch, i| last[ch] = i }

  # 2. Проход с жадным расширением границы
  result = []
  start = 0
  finish = 0

  s.each_char.with_index do |ch, i|
    finish = [finish, last[ch]].max

    if i == finish
      result << finish - start + 1
      start = i + 1
    end
  end

  result
end
```

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

```
s = "ababcbacadefegdehijhklij"
last: {a→8, b→5, c→7, d→14, e→15, f→11, g→13, h→19, i→22, j→23, k→20, l→21}

Пошагово (start=0, finish=0):
  i=0  a → finish=max(0,8)=8
  i=1  b → finish=max(8,5)=8
  i=2  a → finish=max(8,8)=8
  i=3  b → finish=max(8,5)=8
  i=4  c → finish=max(8,7)=8
  i=5  b → finish=max(8,5)=8
  i=6  a → finish=max(8,8)=8
  i=7  c → finish=max(8,7)=8
  i=8  a → finish=max(8,8)=8, i==finish → result<<9, start=9

  i=9  d → finish=max(0,14)=14
  i=10 e → finish=max(14,15)=15
  i=11 f → finish=max(15,11)=15
  i=12 e → finish=max(15,15)=15
  i=13 g → finish=max(15,13)=15
  i=14 d → finish=max(15,14)=15
  i=15 e → finish=max(15,15)=15, i==finish → result<<7, start=16

  i=16 h → finish=max(0,19)=19
  i=17 i → finish=max(19,22)=22
  i=18 j → finish=max(22,23)=23
  i=19 h → finish=max(23,19)=23
  i=20 k → finish=max(23,20)=23
  i=21 l → finish=max(23,21)=23
  i=22 i → finish=max(23,22)=23
  i=23 j → finish=max(23,23)=23, i==finish → result<<8, start=24

Result: [9, 7, 8]
```

## Edge Cases

- **Одна буква во всей строке**: `s = "aaaaa"` → `[5]` — вся строка один блок.
- **Нет повторяющихся букв**: `s = "abcdef"` → `[1, 1, 1, 1, 1, 1]` — каждая буква в своём блоке.
- **Строка из двух одинаковых букв**: `s = "zz"` → `[2]` — один блок.
- **Символы одного класса разбросаны по всей строке**: `s = "abca"` → `[4]` — вся строка один блок (a на 0 и 3).
- **Пустая строка**: `s = ""` → `[]` — корректно: each_char не выполняется, result = [].

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

1. ❌ **Забыть, что last[ch] может быть nil** — в Ruby nil ведёт себя как 0 в `[nil, i].max`, что даёт неверный finish для ещё не встреченного символа. Гарантировано, что мы сначала заполняем last, а потом проходим — поэтому ошибки нет.
2. ❌ **Перепутать start и finish**: `start` — начало текущей части, `finish` — её динамическая правая граница.
3. ❌ **Сбрасывать finish в 0 после каждого блока** — не нужно, цикл сам его перезаписывает.

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

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force intervals | O(n²) | O(n) | У каждой буквы интервал, затем слияние интервалов — то же решение, но сложнее |
| **Last hash + greedy scan** | **O(n)** | **O(1)** | **финальное решение** |

Brute-force через слияние отрезков (interval merge) даёт ту же логику, но дольше писать. Финальное решение — самый короткий и эффективный код.

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

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