Введение в задачу и правила игры 🎵
Привет, рейверы кода! 🎉 Сегодня у нас не просто задача, а настоящий музыкальный баттл! Представьте, что вы диджей на самой крутой вечеринке этого года. Ваша задача — собрать самый длинный и уникальный плейлист, чтобы сломать танцпол и не разочаровать публику. Но есть одно "но": вы не можете использовать одну и ту же песню дважды! Сможете ли вы выдержать это испытание?
Для тех, кто предпочитает более... земные описания: нам нужно найти самую длинную подстроку без повторяющихся символов в данной строке.
Полное условие задачи на LeetCode.
Что нового я узнаю 🧠
- Работа с подстроками
- Слайдинг-виндоу (скользящее окно)
- Применение хеш-таблицы для отслеживания символов
Шаг 1: Подготовка к микшированию 🎚
Первое, что нам нужно сделать, это создать некий "музыкальный архив", где будут храниться уже использованные песни (или символы в нашей строке).
unique_chars = set()
Шаг 2: Проверка заявок и бронирование треков 🎵
Для этого нам потребуются две переменные: start и end. Это будут начало и конец нашего музыкального "окна". Да-да, как в том меме: "Я в этом окне". 🪟
start = 0
end = 0
Шаг 3: Начинаем вечеринку! 🎉
Двигаем наше "окно" по строке, добавляя каждый новый, ещё не встречавшийся символ в unique_chars. Как только находим повтор, двигаем начало "окна".
max_len = 0 # Это для хранения длины самого крутого плейлиста
while end < len(s):
if s[end] not in unique_chars:
unique_chars.add(s[end])
end += 1
max_len = max(max_len, end - start)
else:
unique_chars.remove(s[start])
start += 1
Финальный трек-лист 🎧
Объединяем все шаги в финальный код. Копируй, вставляй, танцуй!
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = 0
end = 0
max_len = 0
unique_chars = set() # Наш музыкальный архив
while end < len(s):
# Двигаем "окно" вправо
while end < len(s) and s[end] not in unique_chars:
unique_chars.add(s[end])
end += 1
max_len = max(max_len, end - start)
# Удаляем первый символ из "окна"
unique_chars.remove(s[start])
start += 1
return max_len
Асимптотика 🤓
Временная сложность: O(n), где n — длина строки.
Пространственная сложность: O(k), где k — размер алфавита (в нашем случае максимум 128 ASCII символов).
Подводные камни 🪨
- Остерегайтесь зацикливания при неправильном перемещении окон
- Не забудьте удалить символы из unique_chars при сдвиге окна
Альтернативные решения 🔄
- Brute Force: Просто перебрать все подстроки и проверить их на уникальность. Но это слишком медленно.
- Dynamic Programming: Хранение длин подстрок в массиве для быстрого доступа.
Анекдот 🤣
Знаете, почему диджеи никогда не становятся программистами? Потому что они не могут устоять перед желанием повторить хороший трек!
Вперед, к новым музыкальным вершинам и кодовым испытаниям! 🎧🚀