Longest Substring Without Repeating Characters

+10

Дана строка s. Найдите самую длинную подстроку — последовательность символов, стоящих рядом друг с другом, — в которой ни один символ не встречается дважды, и верните её длину.

Заглавные и строчные буквы считаются разными символами, поэтому a и A не являются повтором.

Функция

lengthOfLongestSubstring(s: string) → integer

sstring: строка для поиска
Возвращаетinteger: длина самой длинной подстроки без повторяющихся символов

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только английские буквы (строчные и прописные) и цифры.
Заглавные и строчные буквы — разные символы.

Примеры

Ввод: s = "coddycode"
Вывод: 5
Пояснение: В ycode содержится пять разных символов. Если добавить перед ним d, получится dycode, в котором d встречается дважды, а в других последовательностях из пяти или более символов повторов нет.

Ввод: s = "racecar"
Вывод: 4
Пояснение: И в race, и в ecar четыре разные буквы. В каждом наборе из пяти букв одна и та же буква встречается дважды.

Ввод: s = "a1b2a3b"
Вывод: 5
Пояснение: Цифры тоже считаются символами, поэтому в 1b2a3 их пять. В обеих последовательностях из шести символов есть вторая a или вторая b.

Дополнительный вопрос

Что бы ты изменил, если бы s могло содержать любые символы Unicode, а не только буквы и цифры?

Решение

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

Проверь каждую подстроку

Верно, но не успевает на самых больших тестах

Идея

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

Подстрок примерно n²/2, то есть 1.25 × 10^9 при n = 5 × 10^4, а одна проверка может прочитать до n символов: O(n³). Здесь проверка останавливается не позднее чем через 63 символа, поскольку строка содержит всего 62 различных символа, но даже так остаётся более миллиарда проверок.

Алгоритм

Установи best равным 0.
Для каждого начального индекса пройдись по всем конечным индексам от начала до конца строки.
Добавляй символы подстроки в пустое множество по одному и остановись на первом символе, который уже есть в множестве.
Если ни один символ не повторился и подстрока превосходит best, сохрани её длину.
Верни best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Скользящее окно с множеством

Идея

Если в abc нет повторов, для проверки abcd нужен один вопрос: есть ли d среди a, b и c? Множество символов окна сразу на него отвечает.

Передвигай right по одному шагу за раз. Если новый символ уже есть в множестве, удаляй символы слева, пока его прежняя копия не исчезнет, затем добавь его и измерь длину. Ты удаляешь символы, только когда это необходимо, поэтому для каждого right окно — это самая длинная последовательность без повторов, заканчивающаяся на этой позиции, а лучшая подстрока заканчивается где-то в строке. Каждый символ входит в множество один раз и покидает его не более одного раза: O(n).

Алгоритм

Начните с пустого множества, left = 0 и best = 0.
Перемещайте right по каждому индексу.
Пока s[right] находится в множестве, удаляйте s[left] и перемещайте left на один шаг вперёд.
Добавьте s[right] в множество.
Если right - left + 1 больше best, сохраните его.
Верните best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Скользящее окно, перемещающееся к индексу последнего появления

Идея

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

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

Алгоритм

Создайте пустое отображение символов на их последние индексы и установите left = 0 и best = 0.
Перемещайте right по всем индексам, читая символ ch по текущему индексу.
Если ch в последний раз встречался на индексе, большем или равном left, установите left равным этому индексу плюс один.
Запишите right как последний индекс ch.
Если right - left + 1 больше best, сохраните это значение.
Верните best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Ловушки и крайние случаи

Перемещение left назад. В abba более ранняя a с индексом 0 уже находится вне окна, когда ты доходишь до последней a. Переход к индексу 1 возвращает вторую b в окно и дает 3 вместо 2.
Подсчет размера окна как right - left. Оба конца входят в окно, поэтому прибавь единицу.
Сначала преобразовать строку в нижний регистр. Здесь a и A — разные символы, поэтому длина aA равна 2.
Измерение только при появлении повтора. Строка без повторов, например z, никогда не вызовет это условие, и ответ будет равен 0.

Частые вопросы3

Какова временная сложность алгоритма поиска самой длинной подстроки без повторяющихся символов?

Скользящее окно работает за время O(n), где n — длина строки: правая граница считывает каждый символ один раз, а левая граница движется только вперёд. Дополнительная память составляет O(k), где k — количество различных символов, которые может содержать строка, в данном случае 62.

Следует ли использовать хеш-таблицу или массив для хранения последних индексов?

Оба варианта работают за время O(n). При небольшом фиксированном наборе символов, как здесь, массив с индексами по кодам символов позволяет избежать хеширования и работает быстрее.

В чём разница между подстрокой и подпоследовательностью?

Подстрока — это блок символов, расположенных рядом друг с другом, например ode в coddycode. Подпоследовательность может пропускать символы, например cdy. В этой задаче требуется найти подстроку, поэтому подходит окно с двумя границами.

def lengthOfLongestSubstring(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "coddycode"

Ожидаемый вывод

Longest Substring Without Repeating Characters

Функция

Ограничения

Примеры

Подсказки

Решение

Проверь каждую подстроку

Скользящее окно с множеством

Скользящее окно, перемещающееся к индексу последнего появления

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи