Расширение, сжатие и инвариант окна

Окно переменного размера растёт, пока сохраняется нужное свойство, и сжимается, когда свойство нарушено. Разберём конкретную задачу: найти длину самой длинной непрерывной подстроки без повторяющихся символов. Для "abba" ответ равен 2 ("ab" или "ba").

Как максимизировать подстроку без повторов

Нужно выбрать диапазон [left, right], в котором каждый символ встречается ровно один раз, и максимизировать его длину. Подстрока непрерывна: нельзя пропускать символы между границами.

Почему каждый новый старт повторяет прежний поиск

Для каждого начала можно создать пустое множество и расширять конец, пока не встретится повтор. В худшем случае для каждого из n начал просматривается почти весь остаток строки: ожидаемое время O(n²), память O(u), где u — число разных символов в рассматриваемом фрагменте.

Если отдельно проверять каждую из O(n²) подстрок на уникальность, получится ещё более прямой вариант за O(n³). Даже улучшенный квадратичный перебор повторяет работу на сильно перекрывающихся диапазонах.

Какой минимальный префикс мешает текущему символу

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

Последний индекс повтора указывает новую границу

Храним последний индекс каждого символа. Если текущий символ c раньше встречался на позиции p внутри текущего окна, единственный нарушающий повтор исчезнет после сдвига left на p + 1.

Формула left = max(left, last[c] + 1) также учитывает старые появления вне окна: левая граница никогда не должна двигаться назад.

Какие свойства сохраняет исправленное окно

После ремонта на каждой итерации выполняются свойства:

• подстрока text[left..right] не содержит повторов;
• last[c] хранит самый правый уже просмотренный индекс символа c;
• left и right двигаются только вправо;
• best — максимальная длина корректного окна среди всех обработанных правых границ.

Расширяем справа и не возвращаем left назад

1. Начать с left = 0, best = 0 и пустой таблицы last.
2. Последовательно выбирать каждый индекс right и символ c = text[right].
3. Если c уже встречался, обновить left = max(left, last[c] + 1).
4. Записать last[c] = right.
5. Обновить best значением right - left + 1.
6. После прохода вернуть best.

Последние позиции символов в C++ и Python

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>

std::size_t longestUnique(const std::string& text) {
    std::unordered_map<char, std::size_t> last;
    std::size_t left = 0;
    std::size_t best = 0;

    for (std::size_t right = 0; right < text.size(); ++right) {
        const char current = text[right];
        const auto previous = last.find(current);

        if (previous != last.end()) {
            left = std::max(left, previous->second + 1);
        }

        last[current] = right;
        best = std::max(best, right - left + 1);
    }

    return best;
}

int main() {
    assert(longestUnique("abba") == 2);
    assert(longestUnique("tmmzuxt") == 5);
    assert(longestUnique("aaaa") == 1);
    assert(longestUnique("") == 0);
    std::cout << "OK\n";
}

Python 3

def longest_unique(text: str) -> int:
    last: dict[str, int] = {}
    left = 0
    best = 0

    for right, char in enumerate(text):
        if char in last:
            left = max(left, last[char] + 1)

        last[char] = right
        best = max(best, right - left + 1)

    return best


assert longest_unique("abba") == 2
assert longest_unique("tmmzuxt") == 5
assert longest_unique("aaaa") == 1
assert longest_unique("") == 0
print("OK")

Линейное движение границ и модель символов

right проходит строку один раз, а left никогда не уменьшается. Операции хеш-таблицы в среднем занимают O(1), поэтому ожидаемое время — O(n), память — O(u), где u <= n — число разных просмотренных символов.

C++-версия рассматривает std::string как последовательность байтов и подходит для ASCII или другого однобайтового алфавита. Python перебирает Unicode-кодовые точки. Ни одна версия без дополнительной обработки не считает пользовательские графемы вроде составных эмодзи одним символом.

Старый повтор вне окна и многобайтовый текст

• Пустая строка: ответ 0.
• Все символы одинаковы: окно каждый раз сжимается до длины 1.
• Все символы различны: окно растёт до длины всей строки.
• Повтор находится вне текущего окна, как последнее a в "abba": left нельзя возвращать назад.
• Пробелы и знаки пунктуации считаются обычными символами.
• Многобайтовый текст требует заранее определить, что именно считается символом.

Проверяем пустую, уникальную и повторяющуюся строки

• "" → 0.
• "abba" → 2.
• "abcdef" → 6.
• "aaaa" → 1.
• "tmmzuxt" → 5, подстрока "mzuxt".

Когда нарушение можно исправить только сжатием

Ищется самый длинный или короткий непрерывный фрагмент, правая граница естественно идёт вперёд, а нарушение условия можно исправить только сдвигом левой границы вперёд. Для уникальности состояние удобно хранить в множестве или таблице последних индексов.

Где окно теряет монотонность

Окно не подходит для подпоследовательности, где элементы можно пропускать. Оно также не ускоряет задачу автоматически, если после сдвига left условие может непредсказуемо ухудшиться. Например, для числового условия по сумме отрицательные элементы часто разрушают монотонность расширения и сжатия. Для фиксированной длины проще отдельная схема фиксированного окна.

Почему левая граница использует max

Вопрос. Что сломается в "abba", если написать просто left = last[c] + 1 без max?

Ответ. После второго b граница уже равна 2. У последнего a старое вхождение имеет индекс 0 и находится вне окна. Простое присваивание вернёт left к 1 и ошибочно объявит "bba" уникальной. max сохраняет left = 2.

Почему прыжок не пропускает лучший ответ

Вопрос. Почему прыжок сразу на last[c] + 1 не пропускает более длинный корректный ответ?

Ответ. Любое окно, заканчивающееся текущим c и начинающееся не правее прошлого такого же c, содержит повтор. Начало last[c] + 1 — самая левая позиция, которая устраняет именно этот повтор, значит она оставляет максимально длинное допустимое окно с текущей правой границей.

Прослеживаем окно на строке tmmzuxt

Задание. Проследите "tmmzuxt" и после каждого символа запишите right, left и длину окна.

Подсказки. После первого m окно равно "tm". Второй m передвигает left с 0 на 2, после чего окно снова растёт: "mz", "mzu", "mzux", "mzuxt".

Проверка. Максимальная длина равна 5. Последовательность значений best по мере прохода: 1, 2, 2, 2, 3, 4, 5.

Самостоятельная задача о минимальном фрагменте

Задача 1

Дан массив положительных целых чисел и положительный target. Найдите минимальную длину непрерывного подмассива с суммой не меньше target, либо 0, если такого фрагмента нет. Требуется линейное время; объясните, почему положительность входа существенна.

Ремонтируемое нарушение определяет движение окна

Переменное окно работает, когда нарушение можно однозначно «починить» движением левой границы. В задаче об уникальных символах последний индекс повтора точно указывает минимальный необходимый сдвиг.