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

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

s = "abcabcbb"

3

s = "bbbbb"

1

s = "pwwkew"

3

Решение

Наивное решение перебирает все подстроки и для каждой проверяет, есть ли в ней повторы. Это занимает O(n²) или O(n³) и не подходит для строк длины 10⁵.

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

Идея решения:

Поддерживаем окно [left..right] и множество seen символов внутри него.

Идем правой границей по строке. Если s[right] уже есть в seen, окно стало недопустимым: в нем два одинаковых символа. Тогда сдвигаем left вправо и убираем символы из множества, пока дубликат не исчезнет.

После этого добавляем s[right] в множество и обновляем максимальную длину окна.

Основные шаги:

1. Инициализируем множество seen, указатель left = 0 и переменную maxLen = 0.
2. Идем указателем right по строке.
3. Пока s[right] уже есть в seen:
   • удаляем s[left] из множества;
   • увеличиваем left.
4. Добавляем s[right] в seen.
5. Обновляем maxLen = max(maxLen, right - left + 1).
6. Возвращаем maxLen.

Рассмотрим пример:

s = "abcabcbb"

1. right = 2: окно abc, все символы различны. maxLen = 3.

2. right = 3: добавляем вторую a. В окне появился повтор, нужно сузить его слева.

3. Убираем первую a и сдвигаем left. Окно становится bca, все символы снова различны. maxLen остается 3.

4. Продолжаем движение. На right = 6 в окне abcb снова появляется повтор b.

5. Сдвигаем left, пока вторая b не станет единственной. Окно становится cb. Максимум по-прежнему равен 3.

Итог: ответ равен 3.

Оценка сложности

Временная сложность

Указатель right проходит по строке один раз. Указатель left только сдвигается вперед и тоже проходит каждый символ не более одного раза. Добавление и удаление из хеш-множества в среднем занимает O(1).

Итоговая временная сложность: O(n).

Пространственная сложность

В множестве хранятся символы текущего окна. В худшем случае все символы различны, и окно покрывает всю строку.

Пространственная сложность: O(n).

Код решения

Приведем код решения.

func lengthOfLongestSubstring(s string) int {
    seen := map[byte]bool{}
    left := 0
    maxLen := 0
 
    for right := 0; right < len(s); right++ {
        for seen[s[right]] {
            delete(seen, s[left])
            left++
        }
        seen[s[right]] = true
        maxLen = max(maxLen, right-left+1)
    }
 
    return maxLen
}

Итоги

Задача Longest Substring Without Repeating Characters - базовый пример динамического скользящего окна на строках.

1. Суть алгоритма: расширяем окно вправо и храним символы в множестве. Если новый символ уже есть в окне, сдвигаем left, пока повтор не исчезнет.
2. Эффективность:
   • Временная сложность: O(n), так как каждый символ входит в окно и выходит из него не более одного раза.
   • Пространственная сложность: O(n) для множества символов текущего окна.
3. Граничные случаи:
   • Пустая строка: ответ равен 0.
   • Все символы одинаковые: окно всегда длины 1.
   • Все символы различные: ответ равен длине всей строки.
4. Оптимальное решение: мы не проверяем каждую подстроку с нуля, а поддерживаем самое длинное допустимое окно за один проход.