Longest Substring Without Repeating Characters

Средняя№3переменный размер

Дана строка. Найди длину самого длинного куска подряд идущих букв, в котором ни одна буква не повторяется. Наш пример: «abcbdae» — ответ 5, кусок «cbdae».

3 Longest Substring Without Repeating CharactersРазбор · 1×

Пример: s = «abcbdae». Под строкой — словарь: буква и последний индекс, где она была; бледные записи указывают левее left.

0a1b2c3b4d5a6elastc: i—
ещё не дошлиокнотекущая букваповторвышло из окнасамый длинный кусок

Начинаем с пустого словаря: буква → последний индекс, где она была

01/40
сначала · назад · пуск · шаг
Скорость
1function lengthOfLongestSubstring(s):
2 last = empty map
3 left = 0
4 best = 0
5 for right from 0 to len(s) - 1:
6 c = s[right]
7 if c in last and last[c] >= left:
8 left = last[c] + 1
9 last[c] = right
10 best = max(best, right - left + 1)
11 return best
состояние
last
{}
left
–
right
–
c
–
best
–
историянажмите шаг, чтобы вернуться

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

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

  1. Любой кусок без повторов, который кончается на right, может начаться не раньше, чем сразу после прошлой копии s[right]. Поэтому left прыгает прямо туда, а не идёт по одной букве.
  2. Словарь не чистится, в нём может остаться буква, которая уже вышла из окна. Проверка last[c] ≥ left их различает: копия левее left — не повтор, и left никогда не едет назад.
  3. После каждого шага в окне нет повторов, и каждый right измеряется один раз, поэтому самый длинный такой кусок — лучшая из этих длин.

Сложность

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

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

Решить на LeetCode ↗

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