Постановка задачи
Дана строка s, нужно найти длину самой длинной подстроки без повторяющихся символов.
Подход к решению
Для решения этой задачи мы воспользуемся техникой “скользящего окна”. Суть подхода в том, чтобы использовать два указателя, которые будут представлять текущую подстроку, и множество для отслеживания уникальных символов. Если встречаем повторяющийся символ, сдвигаем левый указатель вправо до тех пор, пока не удалим повторяющийся символ из множества.
Алгоритм
Инициализируем переменные: res для хранения максимальной длины подстроки, left для начала окна и seen для уникальных символов.
Проходим по строке с помощью правого указателя:
Если символ под правым указателем уже в seen, сдвигаем левый указатель вправо, удаляя символы из seen, пока не уберем повторяющийся символ.
Добавляем текущий символ под правым указателем в seen.
Обновляем res, если текущая длина окна больше текущего максимума.
Возвращаем результат.
Код решения
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 – размер алфавита.
Этот алгоритм является эффективным решением задачи с использованием техники “скользящее окно”, что позволяет обрабатывать строку за линейное время и сохранять уникальные символы подстроки.