PrepBro
← Назад к вопросам

Максимальная подстрока без повторов

1.0 Junior🔥 131 комментариев
#Python Core

Условие

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

Пример

longest_unique("abcabcbb") → 3 ("abc") longest_unique("bbbbb") → 1 ("b") longest_unique("pwwkew") → 3 ("wke")

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Максимальная подстрока без повторов

Эта классическая задача на технику sliding window (скользящее окно). Задача часто появляется на интервью и требует оптимизации O(n) временной сложности.

Понимание задачи

# Примеры
longest_unique("abcabcbb") → 3  (подстрока "abc")
longest_unique("bbbbb") → 1    (подстрока "b")
longest_unique("pwwkew") → 3   (подстрока "wke")
longest_unique("au") → 2       (подстрока "au")
longest_unique("") → 0         (пустая строка)

Решение 1: Sliding Window (Оптимальное)

def longest_unique_substring(s: str) -> int:
    """Находит длину наибольшей подстроки без повторов.
    
    Args:
        s: str - исходная строка
    
    Returns:
        int - длина максимальной подстроки без повторов
    
    Сложность: O(n) время, O(min(n, 256)) память
    """
    if not s:
        return 0
    
    # Словарь для хранения последнего индекса каждого символа
    char_index = {}
    max_length = 0
    left = 0  # Левый указатель окна
    
    for right in range(len(s)):
        char = s[right]
        
        # Если символ уже встречался И находится в текущем окне
        if char in char_index and char_index[char] >= left:
            # Передвигаем левый указатель
            left = char_index[char] + 1
        
        # Обновляем индекс символа
        char_index[char] = right
        
        # Обновляем максимальную длину
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Примеры
print(longest_unique_substring("abcabcbb"))  # 3 ("abc")
print(longest_unique_substring("bbbbb"))     # 1 ("b")
print(longest_unique_substring("pwwkew"))    # 3 ("wke")
print(longest_unique_substring("au"))        # 2 ("au")
print(longest_unique_substring(""))          # 0

Как работает sliding window

Строка: "abcabcbb"
         0 1 2 3 4 5 6 7

Шаг 1: left=0, right=0 ("a")
  char_index = {"a": 0}
  длина = 1

Шаг 2: left=0, right=1 ("ab")
  char_index = {"a": 0, "b": 1}
  длина = 2

Шаг 3: left=0, right=2 ("abc")
  char_index = {"a": 0, "b": 1, "c": 2}
  длина = 3 (максимум)

Шаг 4: left=0, right=3 ("abca") - "a" повторился!
  char_index["a"] = 0, но 0 >= left (0)
  Передвигаем left: left = 0 + 1 = 1
  Теперь окно: "bca" (индексы 1-3)
  char_index["a"] = 3
  длина = 3

Шаг 5: left=1, right=4 ("bcab") - "b" повторился!
  char_index["b"] = 1, но 1 >= left (1)
  Передвигаем left: left = 1 + 1 = 2
  Теперь окно: "cab" (индексы 2-4)
  char_index["b"] = 4
  длина = 3

И так далее...

Ответ: 3

Решение 2: С сохранением самой подстроки

def longest_unique_with_string(s: str) -> tuple:
    """Возвращает длину и саму подстроку."""
    if not s:
        return 0, ""
    
    char_index = {}
    max_length = 0
    max_start = 0
    left = 0
    
    for right in range(len(s)):
        char = s[right]
        
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        
        current_length = right - left + 1
        if current_length > max_length:
            max_length = current_length
            max_start = left
    
    return max_length, s[max_start:max_start + max_length]

# Использование
length, substring = longest_unique_with_string("abcabcbb")
print(f"Length: {length}, Substring: '{substring}'")  # Length: 3, Substring: 'abc'

Решение 3: Альтернативный подход с set

def longest_unique_set(s: str) -> int:
    """Альтернативная реализация с set (менее эффективна)."""
    if not s:
        return 0
    
    char_set = set()
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        # Удаляем символы с левого края, пока не исчезнет дубликат
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        char_set.add(s[right])
        max_length = max(max_length, len(char_set))
    
    return max_length

# Эта версия медленнее, но более интуитивна

Визуализация для "pwwkew"

"pwwkew"
 012345

right=0, char='p': {"p"} → length=1, max=1
right=1, char='w': {"p","w"} → length=2, max=2
right=2, char='w': повтор! left переходит к индексу 2
              {"w"} → length=1
right=3, char='k': {"w","k"} → length=2
right=4, char='e': {"w","k","e"} → length=3, max=3
right=5, char='w': повтор! left переходит к индексу 4
              {"e","w"} → length=2

Ответ: 3 (подстрока "wke")

Анализ сложности

Солюция со словарём (оптимальная):
- Временная сложность: O(n) - один проход по строке
- Пространственная сложность: O(min(m, n))
  где m = размер алфавита (обычно 256 для ASCII)
  n = длина строки

Солюция с set (медленнее):
- Временная сложность: O(n) - но с большей константой
  (операции удаления на краю могут быть медленнее)
- Пространственная сложность: O(min(m, n))

Брутфорс (не рекомендуется):
- Временная сложность: O(n^3) - проверяем каждую подстроку
- Пространственная сложность: O(n)

Сравнение решений

import timeit

test_string = "abcdefghijklmnopqrstuvwxyz" * 100

time1 = timeit.timeit(
    lambda: longest_unique_substring(test_string),
    number=1000
)
print(f"Dict solution: {time1:.4f}s")

time2 = timeit.timeit(
    lambda: longest_unique_set(test_string),
    number=1000
)
print(f"Set solution: {time2:.4f}s")

# Dict solution обычно в 1.5-2 раза быстрее

Тесты

def test_longest_unique():
    assert longest_unique_substring("abcabcbb") == 3
    assert longest_unique_substring("bbbbb") == 1
    assert longest_unique_substring("pwwkew") == 3
    assert longest_unique_substring("au") == 2
    assert longest_unique_substring("") == 0
    assert longest_unique_substring("a") == 1
    assert longest_unique_substring("abcdefg") == 7
    assert longest_unique_substring("abba") == 2  # "ab" или "ba"
    assert longest_unique_substring("dvdf") == 3  # "vdf"
    print("All tests passed!")

test_longest_unique()

Вариации задачи

1. Найти саму подстроку

def get_longest_unique(s: str) -> str:
    if not s:
        return ""
    
    char_index = {}
    max_length = 0
    max_start = 0
    left = 0
    
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        
        char_index[s[right]] = right
        
        if right - left + 1 > max_length:
            max_length = right - left + 1
            max_start = left
    
    return s[max_start:max_start + max_length]

print(get_longest_unique("abcabcbb"))  # "abc"

2. С ограничением на символы

def longest_with_constraint(s: str, max_chars: int) -> int:
    """Найти подстроку без повторов, не более max_chars уникальных."""
    char_count = {}
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        while len(char_count) > max_chars:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

print(longest_with_constraint("abcabcbb", 2))  # 3 ("ab", "bc")

Ключевые моменты на интервью

  1. Sliding Window — основная техника для этой задачи
  2. Hashmap vs Set — словарь быстрее для больших алфавитов
  3. Off-by-one ошибки — проверяй граничные случаи
  4. Сложность — важна O(n) вместо O(n²) или O(n³)
  5. Пустая строка — не забыть обработать edge case
  6. Повторы — как только встретили повтор, сдвигаем левый указатель

Что может спросить интервьюер

  • Как работает sliding window?
  • Почему используется словарь вместо set?
  • Как найти саму подстроку, а не только длину?
  • Что будет с очень большой строкой?
  • Как адаптировать код для Unicode символов?
  • Можно ли сделать это за один проход?
Максимальная подстрока без повторов | PrepBro