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

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

Ссылка на задачу: https://leetcode.com/problems/longest-substring-without-repeating-characters

Дана строка 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
            res = max(res, right - left + 1)  

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

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

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

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

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

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

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

   • Цикл for итерирует по каждому символу строки, используя указатель right.

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

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

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

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

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

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

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

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

  • left: 1

  • Окно после сокращения: p[ww]kew

  • seen: {'w'}

  • Длина окна: 2

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

  • left: 2

  • Окно после сокращения: pw[w]kew

  • seen: set()

  • Длина окна: 1

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

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

  • left: 3

  • Окно после сокращения: pww[kew]

  • seen: {'k', 'e'}

  • Длина окна: 3

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

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

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

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

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

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