Group Anagrams

O Group Anagrams é um problema clássico de hashing + strings cujo objetivo é agrupar palavras que são anagramas entre si.

---

Enunciado (forma comum)

Dada uma lista de strings strs, agrupe as strings que são anagramas.

Anagramas são palavras formadas pelos mesmos caracteres com as mesmas quantidades, apenas em ordem diferente.

Exemplo

Entrada: ["eat","tea","tan","ate","nat","bat"]
Saída: [
  ["eat","tea","ate"],
  ["tan","nat"],
  ["bat"]
]

A ordem dos grupos ou das palavras dentro deles normalmente não importa.

---

Ideia central

Anagramas compartilham uma assinatura comum. Se duas palavras têm a mesma assinatura, elas pertencem ao mesmo grupo.

O problema se reduz a:

Como gerar uma chave canônica para cada palavra?

---

Estratégias de chave (assinatura)

1. Ordenar os caracteres (mais comum)

• "eat" → "aet"
• "tea" → "aet"

Essa string ordenada é usada como chave em um hash map.

Prós

• Simples
• Fácil de entender

Contras

• Custo de ordenação por palavra

---

2. Contagem de caracteres (mais eficiente)

Cria-se um vetor de frequência (ex.: 26 letras).

• "eat" → (1,0,0,0,1,0,...,1,...)

Esse vetor (convertido em tupla) vira a chave.

Prós

• O(k) por palavra (k = tamanho da palavra)
• Mais eficiente que ordenar

Contras

• Implementação um pouco menos direta

---

Solução 1 — Usando ordenação

Algoritmo

1. Crie um dict (chave → lista de palavras)

2. Para cada palavra:

   • Ordene seus caracteres
   • Use a string ordenada como chave
   • Adicione a palavra ao grupo

3. Retorne os valores do dicionário

Implementação (Python)

from collections import defaultdict
 
def groupAnagrams(strs):
    groups = defaultdict(list)
 
    for word in strs:
        key = ''.join(sorted(word))
        groups[key].append(word)
 
    return list(groups.values())

Complexidade

• Tempo: O(n · k log k)
• Espaço: O(n · k)

Onde:

• n = número de palavras
• k = tamanho médio das palavras

---

Solução 2 — Usando contagem de caracteres (ótima)

Algoritmo

1. Para cada palavra:

   • Crie um array de 26 posições
   • Conte as letras
   • Converta o array em tuple

2. Use essa tupla como chave no hash map

Implementação (Python)

from collections import defaultdict
 
def groupAnagrams(strs):
    groups = defaultdict(list)
 
    for word in strs:
        count = [0] * 26
        for c in word:
            count[ord(c) - ord('a')] += 1
 
        groups[tuple(count)].append(word)
 
    return list(groups.values())

Complexidade

• Tempo: O(n · k)
• Espaço: O(n · k)

---

Comparação rápida

Abordagem	Tempo	Quando usar
Ordenação	O(k log k)	Entrada pequena, simplicidade
Contagem	O(k)	Entrada grande, foco em performance

---

Pontos importantes de entrevista

• A chave precisa ser imutável (por isso tuple, não list)
• Contagem funciona apenas se o alfabeto for limitado (ex.: letras minúsculas)
• É um problema essencialmente de hashing + normalização

---

Padrão algorítmico envolvido

• Hash Map
• Canonical Representation
• Agrupamento por chave derivada

Esse padrão aparece em vários problemas de strings e dados categóricos.