5. Group Anagrams

«Всякая надежная группировка требует канонического инварианта — признака, остающегося неизменным при любых перестановках».
— Брайан Керниган

Группировка анаграмм: Стратегии ключей, аллокации и механика map в Go

Задача Group Anagrams (LeetCode 49) требует разбить массив строк на группы так, чтобы каждая группа содержала только взаимные анаграммы.

Вход:  ["eat", "tea", "tan", "ate", "nat", "bat"]
Выход: [
  ["eat", "tea", "ate"],
  ["tan", "nat"],
  ["bat"]
]

В реальных распределенных архитектурах этот паттерн применяется повсеместно:

• Дедупликация и нормализация текстовых сообщений и логов.
• Группировка запросов в поисковых системах с учетом опечаток и перестановок слов.
• Кластеризация биологических последовательностей (ДНК/РНК мутаций).
• Построение обратных индексов в полнотекстовых движках.

На собеседованиях уровня Middle+/Senior эта задача служит отличным тестом на знание внутренней механики хэш-таблиц (hmap) в Go, понимание сравнимости типов (Comparable types) и способность оптимизировать распределение памяти в куче.

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef warn    fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Input["Входной массив строк strs (размер N, длина K)"]:::entry --> Choice{"Выбор канонического ключа"}:::process

    Choice --> SortKey["1. Сортировка символов:<br/>key = sort(s)<br/>Время O(N * K log K)"]:::process
    Choice --> FreqArray["2. Массив частот [26]byte:<br/>Прямой ключ хэш-карты!<br/>Время O(N * K)"]:::success
    Choice --> StringFreq["3. Сериализация в string:<br/>'1#0#2#...'<br/>O(N * K), но лишний мусор GC"]:::warn

    SortKey --> Map["Группировка в хэш-таблице"]:::accent
    FreqArray --> Map
    StringFreq --> Map

    Map --> Result["Сбор групп в [][]string"]:::success
  

Подход 1: Сортировка символов слова (Каноническая строка)

Самый наглядный подход: отсортировать буквы каждого слова по алфавиту. Для слов "eat", "tea", "ate" каноническим ключом станет строка "aet".

package anagram

import (
    "slices"
)

// GroupAnagramsSort группирует анаграммы через сортировку срезов байт.
// Временная сложность: O(N * K log K), где N — число строк, K — максимальная длина слова.
// Пространственная сложность: O(N * K)
func GroupAnagramsSort(strs []string) [][]string {
    // Предвыделение хэш-таблицы (эвристика начальной емкости)
    groups := make(map[string][]string, len(strs)/2+1)

    // Переиспользуемый буфер байт для снижения аллокаций
    buf := make([]byte, 0, 64)

    for _, s := range strs {
        buf = append(buf[:0], s...)
        slices.Sort(buf) // pdqsort на Go 1.21+

        key := string(buf) // Конвертация в string (ключ хэш-карты)
        groups[key] = append(groups[key], s)
    }

    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }

    return result
}

Подход 2: Фиксированный массив [26]byte как ключ (Go-специфичный шедевр)

Можем ли мы избавиться от множителя $\log K$ при сортировке и прийти к линейной сложности $O(N \cdot K)$?
Да! Для каждого слова можно подсчитать частоты букв.

Но как использовать частоты в качестве ключа хэш-карты?
В Python или Java массив нельзя напрямую использовать как ключ словаря (он мутабелен и нехэшируем). Но в языке Go массивы фиксированного размера являются сравниваемыми типами (Comparable)!

// GroupAnagramsArray использует массив [26]byte прямо в качестве ключа хэш-таблицы.
// Временная сложность: O(N * K) — строго линейная!
// Пространственная сложность: O(N * K)
func GroupAnagramsArray(strs []string) [][]string {
    // Ключ мапы — фиксированный массив [26]byte!
    groups := make(map[[26]byte][]string, len(strs)/2+1)

    for _, s := range strs {
        var count [26]byte
        for i := 0; i < len(s); i++ {
            count[s[i]-'a']++
        }
        // Массив передается по значению (26 байт) прямо в хэш-функцию
        groups[count] = append(groups[count], s)
    }

    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }

    return result
}

Почему map[[26]byte] — идеальный выбор на интервью?

1. Линейная сложность $O(N \cdot K)$: Подсчет частот занимает ровно $K$ шагов, никакой сортировки.
2. Нулевые аллокации строк: Нам не нужно вызывать fmt.Sprintf или strings.Builder, чтобы преобразовать частоты в строку вроде "1#0#2#...".
3. Минимум давления на GC: Массив count живет на стеке, а ключ мапы занимает всего 26 байт прямо внутри бакета hmap.

Под капотом: Механика hmap и цена роста

Когда вы выполняете groups[key] = append(groups[key], s), рантайм Go осуществляет сложный каскад операций:

flowchart LR
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef warn    fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Key["Ключ: [26]byte"]:::accent --> Hash["runtime.memhash26(key)<br/>Аппаратный AES-NI хеш"]:::process
    Hash --> Bucket["Поиск бакета в hmap.buckets"]:::process
    Bucket --> Over{"Коэффициент загрузки<br/>loadFactor > 6.5?"}:::warn

    Over -- "Да" --> Grow["Эвакуация: удвоение бакетов<br/>Дорогая аллокация в куче"]:::warn
    Over -- "Нет" --> Insert["Запись значения в бакет"]:::process

    Insert --> AppendSlice["groups[key] = append(...)<br/>Возможный рост внутреннего слайса"]:::success
  

1. Хэширование: Для ключа [26]byte рантайм использует специализированную ассемблерную инструкцию memhash (часто с использованием аппаратного AES-NI).
2. Коэффициент загрузки (Load Factor): Когда среднее число элементов на бакет превышает 6.5, хэш-таблица инициирует инкрементальное удвоение количества бакетов (hashGrow).
3. Предвыделение (Capacity Hint): Передача подсказки размера make(map[...], len(strs)/2+1) гарантирует, что таблица выделит достаточное количество бакетов сразу, предотвратив дорогие фазы эвакуации памяти.

Сравнение подходов

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

Резюме

• Канонический ключ — основа решения задач на группировку эквивалентных структур.
• Сортировка слов дает надежное решение за $O(N \cdot K \log K)$, универсальное для любых алфавитов.
• Использование сравниваемого типа [26]byte в качестве ключа хэш-карты — визитная карточка профессионального Go-инженера: строго линейная сложность $O(N \cdot K)$ и ноль аллокаций на формирование ключа.
• Предвыделение емкости хэш-карты и итогового слайса существенно снижает накладные расходы на сборщик мусора.

В следующей лекции мы перейдем к синтаксическому анализу и работе со стеком в строках: 6. Decode String, где научимся распаковывать рекурсивные вложенные структуры без риска падения по Stack Overflow.