Самая длинная подстрока без повторяющихся символов

Условие

Дана строка s. Необходимо найти длину самой длинной подстроки без повторяющихся символов.

Примеры

Входная строка: "abcabcbb". Результат: 3. Подстрока: "abc".
Входная строка: "bbbbb". Результат: 1. Подстрока: "b".
Входная строка: "pwwkew". Результат: 3. Подстрока: "wke".

Решение

Создадим переменные start и max_len, равные 0.
Создадим пустой словарь char_dict, который будет хранить индексы символов.
Проходим по строке s в цикле:
- Если символ уже есть в словаре и его индекс больше или равен start, то обновляем start как индекс следующего после последнего вхождения этого символа.
- Обновляем max_len как максимум между текущим значением max_len и разностью текущего индекса и start + 1.
- Обновляем значение символа в словаре на текущий индекс.
Возвращаем max_len.

Пример

Пусть дана строка "pwwkew".

Шаг	Символ	Start	Max_len	Словарь
0	p	0	1	{'p': 0}
1	w	1	2	{'p': 0, 'w': 1}
2	w	2	2	{'p': 0, 'w': 2}
3	k	2	3	{'p': 0, 'w': 2, 'k': 3}
4	e	2	3	{'p': 0, 'w': 2, 'k': 3, 'e': 4}
5	w	3	3	{'p': 5, 'w': 3, 'k': 4, 'e': 2}

Максимальная длина подстроки без повторяющихся символов равна 3.

Код

def longest_substring(self, s: str) -> int:
    start = 0
    max_len = 0
    char_dict = {}

    for i, char in enumerate(s):
        if char in char_dict and char_dict[char] >= start:
            start = char_dict[char] + 1
        max_len = max(max_len, i - start + 1)
        char_dict[char] = i

    return max_len