Словари, множества и скользящее окно

В журнале запросов нужно найти самый длинный фрагмент без повторяющегося пользователя. Перебирать все начала и заново проверять каждый фрагмент дорого. Запомним последнее появление пользователя и будем двигать левую границу только вперёд.

Как словарь помогает найти значение

Словарь связывает ключ с результатом. Множество отвечает только на вопрос присутствия; в Go его можно представить map[string]struct{}. Хеш-таблица вычисляет хеш ключа и по нему выбирает область хранения. Разные ключи могут иметь одинаковый хеш: коллизия требует проверки равенства самих ключей. Хеш не является уникальным идентификатором по определению.

Ожидаемое или амортизированное O(1) поиска зависит от реализации, заполнения таблицы и модели ключей. Спецификация map Go не обещает универсальную худшую границу O(1). Хеширование длинной строки имеет цену по её длине. Для инженерного расчёта отдельно учитывайте размер ключа и число записей.

counts := map[string]int{}
for _, name := range []string{"anna", "boris", "anna"} {
    counts[name]++
}
value, exists := counts["dina"]
// value == 0, exists == false

Нулевое значение и отсутствие не всегда одно и то же. Если ноль допустим как настоящий результат, нужен второй результат чтения map. Порядок обхода map не задан; сортируйте ключи перед формированием детерминированного отчёта.

Область без повторов

Пусть строка состоит из символов, которые здесь считаем кодовыми точками Unicode, то есть rune. Графемный кластер — видимый символ вроде буквы с отдельным знаком — может состоять из нескольких rune. Эта модель не измеряет число пользовательских графем. Индексация строки по байтам подходит для ASCII, но ломает такую формулировку на кириллице.

last := map[rune]int{}
left, best := 0, 0
for right, c := range []rune(s) {
    if previous, ok := last[c]; ok && previous >= left {
        left = previous + 1
    }
    last[c] = right
    if size := right-left+1; size > best { best = size }
}

Перед обработкой очередной позиции [left,right) не содержит повторений. Если c уже внутри окна, всё до предыдущего c включительно нужно исключить. Если c встречалось раньше left, менять границу не требуется. Условие previous >= left не даёт границе уйти назад.

На abba: после a,b длина 2. Второе b двигает left с 0 на 2. Последнее a раньше встречалось на 0, вне текущего окна; left остаётся 2. Ответ 2. Если безусловно присваивать previous+1, left вернётся к 1 и ошибочно примет bba.

Стоимость и память

Каждая правая позиция обрабатывается один раз, левая не откатывается. В принятой модели операций словаря — O(n) времени. Map хранит O(k) последних позиций для k различных rune. В этом коде преобразование []rune(s) дополнительно требует O(n) памяти, даже если алфавит маленький. Утверждение O(k) для всей дополнительной памяти было бы неверным.

Практика

Реализуйте собственный LongestUnique в новом файле exercises. Не копируйте эталон до своей попытки. Проверьте пустую строку, abba, aaaa, abcabcbb, абва и смесь кириллицы с ASCII. Отдельно напишите медленный эталон: для каждого начала расширяйте множество до первого повтора. Сравните результаты на всех строках длины до 6 над алфавитом a,b,c.

Критерии готовности: объяснено значение left; она не убывает; повтор за окном не влияет; договор rune явно записан; карта не выдаётся за отсортированную структуру. Практика — 45 минут.

Разбор

Ожидаемые длины: пустая строка 0, abba 2, aaaa 1, abcabcbb 3, абва 3. Двойной цикл не запрещён как тестовый эталон: на маленьких входах его простота помогает независимо проверить оптимизацию. Сложность тестового эталона не меняет сложность основной функции.

Источники: Go: maps, Go: строки и rune, Princeton: хеш-таблицы.