Длина самой длинной подстроки без повторов

Подходы к решению задачи поиска длины самой длинной подстроки без повторов

Это классическая задача на использование структуры данных для хранения элементов и оптимизацию проверки повторений. Основная идея: нам нужно найти подстроку с максимальной длиной, в которой все символы уникальны. Рассмотрим основные стратегии решения.

1. Брутфорс (Brute Force) — неэффективный подход

Можно перебрать все возможные подстроки и проверить их на уникальность символов.

def longest_substring_bruteforce(s: str) -> int:
    max_len = 0
    
    for i in range(len(s)):
        for j in range(i+1, len(s)+1):
            substring = s[i:j]
            if len(set(substring)) == len(substring):
                max_len = max(max_len, len(substring))
    
    return max_len

Проблемы:

• Временная сложность O(n³) — два цикла для подстрок O(n²) и проверка через set O(n)
• Не подходит для больших строк

2. Оптимизированный подход с использованием Hash Set и Sliding Window

Sliding Window — это ключевая техника для подобных задач. Мы поддерживаем окно (подстроку) между индексами left и right, где все символы уникальны.

def longest_substring_hashset(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 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_len = max(max_len, right - left + 1)
    
    return max_len

Анализ:

• Hash Set хранит уникальные символы текущего окна
• При встрече повторяющегося символа сдвигаем левый индекс left, удаляя символы из set
• Временная сложность: O(n) в среднем случае
• Сложность по памяти: O(min(n, m)), где m — размер алфавита (например, 26 для английских букв)

3. Более оптимизированный подход с использованием Hash Map

Вместо медленного удаления символов из set по одному, можно хранить в Hash Map последние позиции символов и сразу перемещать left.

def longest_substring_hashmap(s: str) -> int:
    char_index_map = {}
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        if s[right] in char_index_map:
            left = max(left, char_index_map[s[right]] + 1)
        char_index_map[s[right]] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

Преимущества:

• Временная сложность: строго O(n)
• Сразу перемещаем left на позицию после последнего вхождения повторяющегося символа
• Не требует цикла while внутри основного цикла

4. Решение с использованием массива фиксированного размера (для ограниченного алфавита)

Если известно, что символы принадлежат к ограниченному набору (например, ASCII), можно использовать массив вместо Hash Map.

def longest_substring_array(s: str) -> int:
    last_index = [-1] * 128  # Для ASCII
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        char_index = ord(s[right])
        if last_index[char_index] >= left:
            left = last_index[char_index] + 1
        last_index[char_index] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

Применение:

• Особенно эффективно для английских букв, цифр, ASCII символов
• Сложность по памяти: O(1) — фиксированный массив
• Быстрее Hash Map благодаря отсутствию коллизий и вычислений hash

Выводы и рекомендации для собеседования

1. Объясните логику: задача сводится к поиску максимального окна с уникальными символами
2. Предложите прогрессивные решения: от brute force к оптимальным
3. Выберите оптимальное решение: Hash Map или фиксированный массив (в зависимости от условий)
4. Упомяните ключевые термины: Sliding Window, Hash Set/Map, Time/Space Complexity
5. Оцените сложность: O(n) время, O(k) память (k — размер алфавита)

Пример полного ответа на собеседовании: "Я решаю эту задачу с помощью техники Sliding Window. Использую Hash Map для записи последних позиций символов. Когда встречаю повтор символа, сдвигаю начало окна на позицию после его предыдущего вхождения. Это дает линейную сложность O(n) и эффективно по памяти."