Длина самой длинной подстроки без повторений в Python: скользящее окно

Разбираем скользящее окно в Python для поиска длины самой длинной подстроки без повторений: частые ошибки (None, return, set) и готовый рабочий код.

При реализации скользящего окна для поиска длины самой длинной подстроки без повторяющихся символов частый признак неверного решения — в терминале выводится None вместо числа. Обычно это указывает на отсутствующий return и несколько типичных ошибок подхода со скользящим окном. Ниже — краткий разбор, что идет не так и как правильно выстроить логику.

Рабочий пример

Вариант ниже использует динамическое множество, два указателя и возвращает вычисленную длину. Он полностью сохраняет поведение скользящего окна.

def longest_unique_span(text):
    seen_chars = set()
    best_len = 0
    left = 0
    for right in range(len(text)):
        while text[right] in seen_chars:
            seen_chars.remove(text[left])
            left += 1
        seen_chars.add(text[right])
        best_len = max(best_len, right - left + 1)
    return best_len
if __name__ == "__main__":
    sample = "abcabcbb"
    print(longest_unique_span(sample))  
    # вывод: 3

Что пошло не так и почему это происходит

Если печатается None, значит функция завершилась без возврата значения. В Python функция без явного return по умолчанию возвращает None — именно он и попадает в терминал. Чтобы исправить, нужно в конце вернуть вычисленную длину.

Другая ошибка — заранее инициализировать множество всеми символами. Подход со скользящим окном строится на динамическом расширении и сужении окна по мере итерации, поэтому множество должно начинаться пустым и обновляться по ходу.

Наконец, добавление индексов во множество вместо символов ломает всю логику обнаружения дублей. Нужно отслеживать реальные элементы окна, то есть на каждом шаге добавлять символ в текущей позиции, а не саму позицию.

Исправление

Решение использует два указателя, задающих границы окна. Правый указатель движется по строке. Если текущий символ уже находится внутри окна, левый указатель сдвигается вперед, по пути удаляя символы из множества, пока дубликат не исчезнет. Затем текущий символ добавляется, а максимальная длина обновляется размером текущего окна. В конце функция возвращает найденную максимальную длину — это устраняет вывод None и дает ожидаемый результат.

Почему это важно

Правильная механика скользящего окна критична для корректности. Возврат результата исключает None в выводе, динамическое множество гарантирует, что окно отражает текущую подстроку, а работа с символами, а не индексами, делает проверку на дубликаты точной.

Выводы

Всегда возвращайте вычисленное значение из функции, чтобы в терминале появлялось ожидаемое число. Формируйте состояние окна динамически, а не заранее. В множестве отслеживайте символы, а не индексы. И держите логику с двумя указателями строгой: расширяйте окно правым указателем, сжимайте слева при появлении дубликата, обновляйте максимальную длину — и повторяйте. С этими частями на месте алгоритм стабильно находит длину самой длинной подстроки без повторяющихся символов.