Partition Labels

Средняя№763

Дана строка из строчных букв. Разрежьте её на как можно больше частей так, чтобы каждая буква была только в одной части, и верните длины частей по порядку. Наш пример: «cabcdbefegfh» — ответ [6, 5, 1]: «cabcdb», «efegf» и «h».

763 Partition LabelsРазбор · 1×

Пример: «cabcdbefegfh». end — докуда текущая часть обязана дотянуться; дуга идёт от i до последнего появления его буквы.

0c1a2b3c4d5b6e7f8e9g10f11hsizes—
ещё не дошлиобязано войти в текущую частьтекущий индекс iв готовой части

Последний индекс каждой буквы: c 3, a 1, b 5, d 4, e 8, f 10, g 9, h 11

01/47
сначала · назад · пуск · шаг
Скорость
1function partitionLabels(s):
2 last = the last index of each letter in s
3 sizes = []
4 start = 0
5 end = 0
6 for i from 0 to len(s) - 1:
7 end = max(end, last[s[i]])
8 if i == end:
9 add end - start + 1 to sizes
10 start = i + 1
11 return sizes
состояние
sizes
–
start
–
end
–
i
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Часть, в которой есть буква, должна дотянуться до её последнего появления. Поэтому end — самое дальнее последнее появление букв этой части — и есть самая короткая её длина.
  2. Когда i дошёл до end, ни одна буква части дальше не встречается, и резать здесь можно. Разрез в первом же таком месте оставляет больше всего места следующим частям, и частей выходит больше всего.
  3. Как reach на карточке, end внутри части только растёт, поэтому хватает одного прохода и одного числа.

Сложность

Время O(n): один проход ради последних индексов и один, чтобы резать. Память O(1): последний индекс не больше чем у 26 букв.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.