Решение задачи с собеседования Longest Substring Without Repeating Characters [+ ВИДЕО]27.07.2024 10:30

2df93f27e960dc15331943f15d84fe7d

Постановка задачи

Дана строка s, нужно найти длину самой длинной подстроки без повторяющихся символов.

Подход к решению

Для решения этой задачи мы воспользуемся техникой «скользящего окна». Суть подхода в том, чтобы использовать два указателя, которые будут представлять текущую подстроку, и множество для отслеживания уникальных символов. Если встречаем повторяющийся символ, сдвигаем левый указатель вправо до тех пор, пока не удалим повторяющийся символ из множества.

Алгоритм

  1. Инициализируем переменные:  res для хранения максимальной длины подстроки,  left для начала окна и seen для уникальных символов.

  2. Проходим по строке с помощью правого указателя:

    • Если символ под правым указателем уже в seen, сдвигаем левый указатель вправо, удаляя символы из seen, пока не уберем повторяющийся символ.

    • Добавляем текущий символ под правым указателем в seen.

    • Обновляем res, если текущая длина окна больше текущего максимума.

  3. Возвращаем результат.

Код решения

class Solution:
    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

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

  1. Инициализация переменных:

    • res хранит максимальную длину подстроки без повторяющихся символов.

    • left указывает на начало текущего окна.

    • seen хранит уникальные символы текущего окна.

  2. Итерация по строке:

  3. Обнаружение повторяющихся символов:

    • Внутри цикла while проверяем, есть ли текущий символ в множестве seen. Если да, то удаляем символ под левым указателем из множества и сдвигаем левый указатель вправо.

  4. Добавление уникального символа:

  5. Обновление результата:

  6. Возвращение результата:

Визуализация решения

Рассмотрим строку 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

  • Сокращение окна:

  • Сокращение окна:

  • Окно после обновления результата: 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

  • Сокращение окна:

  • Окно после обновления результата: pww[kew]

  • Текущий максимум: 3

Асимптотическая сложность

  • Сложность по времени: O (n). Каждый символ строки добавляется и удаляется из множества не более одного раза.

  • Сложность по памяти: O (min (n, m)), где n — длина строки, m — размер алфавита.

Этот алгоритм является эффективным решением задачи с использованием техники «скользящее окно», что позволяет обрабатывать строку за линейное время и сохранять уникальные символы подстроки.

© Habrahabr.ru