Почему это работает
- Любой кусок без повторов, который кончается на right, может начаться не раньше, чем сразу после прошлой копии s[right]. Поэтому left прыгает прямо туда, а не идёт по одной букве.
- Словарь не чистится, в нём может остаться буква, которая уже вышла из окна. Проверка last[c] ≥ left их различает: копия левее left — не повтор, и left никогда не едет назад.
- После каждого шага в окне нет повторов, и каждый right измеряется один раз, поэтому самый длинный такой кусок — лучшая из этих длин.
Сложность
Время O(n): один проход, поиск в словаре O(1), а left только прыгает вперёд. Память O(k), где k — число разных букв.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗