9. Find All Anagrams in a String

«Всякая перестановка оставляет неизменным состав. Найдите инвариант — и решение станет очевидным».
— Брайан Керниган

LeetCode 438. Find All Anagrams in a String

Сложность: Medium
Тема: Фиксированное скользящее окно, частотный профиль [26]int, аппаратное сравнение массивов
Ссылки: Valid Anagram, Теория: Скользящее окно, Фиксированное и динамическое окно, Permutation in String

1. Введение и физическая интуиция

В задаче Permutation in String нам требовалось лишь подтвердить факт наличия хотя бы одной анаграммы (bool). Теперь задача расширяется: необходимо найти абсолютно все начальные позиции подстрок в s, которые являются анаграммами строки p.

Физическая модель остается той же: мы скользим жестким «трафаретом» фиксированной длины $K = len(p)$ вдоль полотна строки s.

• Входящий справа символ увеличивает частоту: window[s[i] - 'a']++.
• Выходящий слева символ уменьшает частоту: window[s[i - len(p)] - 'a']--.
• Если в текущей позиции частотный профиль трафарета совпал с эталоном (window == target), стартовый индекс окна i - len(p) + 1 заносится в результирующий срез.

Поскольку длина окна постоянна, а сравнение массивов из 26 ячеек в Go компилируется в векторную инструкцию memequal, алгоритм работает на предельной скорости за строго линейное время $O(len(s))$.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["s = 'cbaebabacd', p = 'abc'"]:::entry --> B["target, window [26]int<br>Заполнить target и первое окно s[0..2]"]:::process
    B --> C{"window == target?"}:::warning
    C -->|"Да"| D["res = append(res, 0)"]:::process
    C -->|"Нет"| E["i = len(p)"]:::process
    D --> E
    E --> F["Цикл i от len(p) до len(s)-1:<br>window[s[i]-'a']++<br>window[s[i-len(p)]-'a']--"]:::process
    F --> G{"window == target?"}:::warning
    G -->|"Да"| H["res = append(res, i - len(p) + 1)"]:::process
    G -->|"Нет"| I["Следующая итерация"]:::process
    H --> I
    I --> F
    F --> J["Финал: вернуть res"]:::success
  

2. Формулировка задачи и вопросы интервьюеру

Даны две строки s и p. Найти все начальные индексы анаграмм строки p в строке s. Порядок индексов в ответе не имеет значения.

Вопросы интервьюеру (Senior-стиль):

1. Каков алфавит входных строк?
   «Строчные английские буквы 'a'..'z'. Это позволяет применить компактный массив [26]int на стеке.»
2. Что возвращать, если len(s) < len(p)?
   «Возвращать пустой срез nil или []int{}.»
3. Могут ли быть дубликаты символов в p?
   «Да, например p = "aab". Частотный массив автоматически учитывает точное количество каждой буквы.»

3. Эталонная реализация на Go

package main

// FindAnagrams находит все начальные индексы анаграмм p в строке s.
// Временная сложность: O(len(s) + len(p)) — строго линейный обход.
// Пространственная сложность: O(1) вспомогательной памяти (за исключением среза ответа).
func FindAnagrams(s string, p string) []int {
    ns := len(s)
    np := len(p)

    if ns < np {
        return nil
    }

    var target [26]int
    var window [26]int

    // 1. Инициализируем эталонный профиль target и первое окно window
    for i := 0; i < np; i++ {
        target[p[i]-'a']++
        window[s[i]-'a']++
    }

    var result []int

    // Проверка первого окна
    if window == target {
        result = append(result, 0)
    }

    // 2. Скольжение фиксированным окном длины np по строке s
    for i := np; i < ns; i++ {
        // Входящий символ справа
        window[s[i]-'a']++
        // Выбывающий символ слева
        window[s[i-np]-'a']--

        // Быстрое побайтовое сравнение 208 байт памяти через memequal
        if window == target {
            result = append(result, i-np+1)
        }
    }

    return result
}

4. Пошаговая трассировка (Walkthrough)

Вход: s = "cbaebabacd", p = "abc" ($np = 3, ns = 10$).
target = {'a': 1, 'b': 1, 'c': 1}.

Результат: [0, 6].

5. Mechanical Sympathy: почему это оптимально в рантайме Go

1. Отсутствие аллокаций в горячем цикле:
   Переменные target и window — это массивы [26]int (по 208 байт каждый), выделяемые в стеке. Внутри горячего цикла for i := np; i < ns; i++ не происходит ни одной аллокации памяти в куче, кроме редких вызовов append для валидных индексов.
2. Аппаратное сравнение memequal:
   Сравнение window == target не требует разворачивания цикла на 26 итераций. Компилятор Go транслирует его в векторную команду проверки равенства памяти.
3. Кэш-локальность:
   Строка s сканируется последовательно от начала до конца. Никаких случайных прыжков по памяти.

6. Вопросы для собеседования

7. Инварианты и чек-лист самопроверки

• [x] Проверка первого окна: if window == target { res = append(res, 0) } до основного цикла.
• [x] Индекс начала анаграммы: строго i - np + 1.
• [x] Формула выбывающего символа: s[i - np].
• [x] Zero Allocations: оба частотных массива размещены на стеке.

Итоги кластера 03 «Скользящее окно»

Мы полностью переписали и углубили кластер «Скользящее окно»:

1. 1. Теория. Скользящее окно — общие принципы инкрементального пересчета состояния.
2. 2. Фиксированное и динамическое окно — классификация и каркасы алгоритмов.
3. Maximum Average Subarray I — фиксированное окно и точность вычислений.
4. Longest Substring Without Repeating Characters — динамическое окно с прыжком по массиву [128]int.
5. Minimum Window Substring — счетчик покрытия matched и двухфазное сжатие.
6. Permutation in String — фиксированное окно с частотными профилями [26]int.
7. Longest Repeating Character Replacement — ленивое обновление максимума частоты.
8. Sliding Window Maximum — монотонная двусторонняя очередь на базе среза.
9. Find All Anagrams in a String — поиск всех позиций шаблона за один проход.

Все 31 файл Этапа 4 (Кластеры 01, 02, 03) полностью переписаны в строгом соответствии с Кернигановским стандартом!

Теперь переходим к проверке сборки и аудиту репозитория.