Код Senior Жадные обновлено
Разбиение строки на части
Условие
Разбей строку на максимальное число частей так, чтобы каждая буква встречалась только в одной части. Верни длины частей.
Примеры
partitionLabels("ababcbacadefegdehijhklij") // [9, 7, 8]
partitionLabels("a") // [1]
partitionLabels("") // []
Как подойти
Два прохода: последние вхождения, затем жадное расширение границы. Момент i === end - это точка, после которой ни одна встреченная буква больше не появится. Тот же приём применяется при слиянии диапазонов и планировании.
Подсказки: 2
- Сначала запомни последнюю позицию каждой буквы.
- Часть заканчивается там, где текущий индекс догнал самую дальнюю обязательную позицию.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.