Почему это работает
- Часть, в которой есть буква, должна дотянуться до её последнего появления. Поэтому end — самое дальнее последнее появление букв этой части — и есть самая короткая её длина.
- Когда i дошёл до end, ни одна буква части дальше не встречается, и резать здесь можно. Разрез в первом же таком месте оставляет больше всего места следующим частям, и частей выходит больше всего.
- Как reach на карточке, end внутри части только растёт, поэтому хватает одного прохода и одного числа.
Сложность
Время O(n): один проход ради последних индексов и один, чтобы резать. Память O(1): последний индекс не больше чем у 26 букв.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗