Решение задачи #3. Python LeetCode, Longest substring without repeating characters

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: Longest substring without repeating characters.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Дана строка s. Найдите длину самой длинной подстрока без повторения символов.

Решение:

Python

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # Словарь для отслеживания последней позиции каждого символа
        char_index = {}
        # Два указателя: начало текущей подстроки и максимальная длина
        start = 0
        max_length = 0

        # Проходим по строке, символ за символом
        for i, char in enumerate(s):
            # Если символ уже встречался и находится в текущей подстроке
            if char in char_index and char_index[char] >= start:
                # Обновляем начало подстроки, пропуская повторяющийся символ
                start = char_index[char] + 1
            
            # Обновляем последнюю позицию текущего символа
            char_index[char] = i
            
            # Вычисляем длину текущей подстроки и обновляем максимальную длину
            max_length = max(max_length, i - start + 1)
        
        return max_length

Объяснение кода

Мы хотим найти длину самой длинной подстроки строки s, которая не содержит повторяющихся символов. Используем метод двух указателей (sliding window) для оптимального решения задачи:

Один указатель (start) отслеживает начало текущей подстроки.
Другой указатель (i) проходит по каждому символу строки.

Логика:
Если символ повторяется, перемещаем start за последний повтор.
Подсчитываем длину текущей подстроки (i - start + 1).
Обновляем максимальную длину.

Источник решения: hdhai.com

Добавьте Hdhai в избранное и вы будете чаще видеть наши последние новости на главной Дзена и в разделе «Новости партнёров» или читайте нас в Telegram в привычном для вас формате.