Постановка задачи
Дана строка s
, нужно найти длину самой длинной подстроки без повторяющихся символов.
Подход к решению
Для решения этой задачи мы воспользуемся техникой «скользящего окна». Суть подхода в том, чтобы использовать два указателя, которые будут представлять текущую подстроку, и множество для отслеживания уникальных символов. Если встречаем повторяющийся символ, сдвигаем левый указатель вправо до тех пор, пока не удалим повторяющийся символ из множества.
Алгоритм
-
Инициализируем переменные:
res
для хранения максимальной длины подстроки,left
для начала окна иseen
для уникальных символов. -
Проходим по строке с помощью правого указателя:
-
Если символ под правым указателем уже в
seen
, сдвигаем левый указатель вправо, удаляя символы изseen
, пока не уберем повторяющийся символ. -
Добавляем текущий символ под правым указателем в
seen
. -
Обновляем
res
, если текущая длина окна больше текущего максимума.
-
-
Возвращаем результат.
Код решения
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: res = 0 left = 0 seen = set() for right in range(len(s)): right_char = s[right] while right_char in seen: left_char = s[left] seen.remove(left_char) left += 1 seen.add(right_char) res = max(res, right - left + 1) return res
Объяснение кода
-
Инициализация переменных:
-
res
хранит максимальную длину подстроки без повторяющихся символов. -
left
указывает на начало текущего окна. -
seen
хранит уникальные символы текущего окна.
-
-
Итерация по строке:
-
Цикл
for
итерирует по каждому символу строки, используя указательright
.
-
-
Обнаружение повторяющихся символов:
-
Внутри цикла
while
проверяем, есть ли текущий символ в множествеseen
. Если да, то удаляем символ под левым указателем из множества и сдвигаем левый указатель вправо.
-
-
Добавление уникального символа:
-
После удаления всех повторяющихся символов из текущего окна, добавляем текущий символ в множество
seen
.
-
-
Обновление результата:
-
Вычисляем длину текущего окна и обновляем
res
, если текущая длина больше.
-
-
Возвращение результата:
-
По завершении цикла возвращаем максимальную длину подстроки без повторяющихся символов.
-
Визуализация решения
Рассмотрим строку s = "pwwkew"
и визуализируем шаги решения задачи, показывая текущее состояние скользящего окна.
Шаги выполнения:
Итерация 0:
-
Текущий символ: p
-
Окно: [p]wwkew
-
seen: set()
-
Длина окна: 1
-
Окно после обновления результата: [p]wwkew
-
Текущий максимум: 1
Итерация 1:
-
Текущий символ: w
-
Окно: [pw]wkew
-
seen: {‘p’}
-
Длина окна: 2
-
Окно после обновления результата: [pw]wkew
-
Текущий максимум: 2
Итерация 2:
-
Текущий символ: w
-
Окно: [pww]kew
-
seen: {‘w’, ‘p’}
-
Длина окна: 3
-
Сокращение окна:
-
left: 1
-
Окно после сокращения: p[ww]kew
-
seen: {‘w’}
-
Длина окна: 2
-
-
Сокращение окна:
-
left: 2
-
Окно после сокращения: pw[w]kew
-
seen: set()
-
Длина окна: 1
-
-
Окно после обновления результата: pw[w]kew
-
Текущий максимум: 2
Итерация 3:
-
Текущий символ: k
-
Окно: pw[wk]ew
-
seen: {‘w’}
-
Длина окна: 2
-
Окно после обновления результата: pw[wk]ew
-
Текущий максимум: 2
Итерация 4:
-
Текущий символ: e
-
Окно: pw[wke]w
-
seen: {‘w’, ‘k’}
-
Длина окна: 3
-
Окно после обновления результата: pw[wke]w
-
Текущий максимум: 3
Итерация 5:
-
Текущий символ: w
-
Окно: pw[wkew]
-
seen: {‘w’, ‘k’, ‘e’}
-
Длина окна: 4
-
Сокращение окна:
-
left: 3
-
Окно после сокращения: pww[kew]
-
seen: {‘k’, ‘e’}
-
Длина окна: 3
-
-
Окно после обновления результата: pww[kew]
-
Текущий максимум: 3
Асимптотическая сложность
-
Сложность по времени: O(n). Каждый символ строки добавляется и удаляется из множества не более одного раза.
-
Сложность по памяти: O(min(n, m)), где n — длина строки, m — размер алфавита.
Этот алгоритм является эффективным решением задачи с использованием техники «скользящее окно», что позволяет обрабатывать строку за линейное время и сохранять уникальные символы подстроки.
ссылка на оригинал статьи https://habr.com/ru/articles/831880/
Добавить комментарий