Самая длинная подстрока без повторяющихся символов
Дана строка s
, найдите длину самой длинной подстроки без повторяющихся символов.
Подстрока - это непрерывная последовательность символов внутри строки.
Пример 1:
Input: s = "abcabcbb"
Output: 3
Объяснение: Самая длинная подстрока без повторов - "abc", длина = 3.
Пример 2:
Input: s = "bbbbb"
Output: 1
Объяснение: Самая длинная подстрока без повторов - "b", длина = 1.
Рекомендуемая временная и пространственная сложность
Оптимальное решение имеет временную сложность O(n)
и пространственную сложность O(k)
, где n
— длина строки, а k
— размер набора возможных символов.
Подсказка 1
Попробуйте использовать технику скользящего окна с двумя указателями для отслеживания текущей подстроки.
Подсказка 2
Используйте хеш-множество для быстрой проверки наличия повторяющихся символов в текущем окне.