Padrão 1: Contagem de caracteres (anagramas)
Duas palavras são anagramas quando têm exatamente os mesmos caracteres, em qualquer ordem. A ferramenta que captura isso é o mapa de frequência — a "impressão digital" de uma string que ignora a ordem.
Tente primeiro: Valid Anagram
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dadas duas strings s e t, retorne true se t for um anagrama de s (mesmos caracteres, em qualquer ordem).
Exemplo: s = "listen", t = "silent" → true. s = "rat", t = "car" → false.
Tentou? Comparar todas as permutações é O(k!) — inviável. Ordenar as duas strings e comparar funciona (O(k log k)), mas há algo ainda mais direto. A teoria abaixo mostra a "assinatura" que identifica anagramas em O(n).
A teoria: a assinatura de frequência
Como saber se "listen" e "silent" são a mesma coisa rearranjada? Comparar
ordem não ajuda — a ordem é justamente o que muda. O que não muda é
quantas vezes cada letra aparece. Esse vetor de contagens é a assinatura:
"listen" → {l:1, i:1, s:1, t:1, e:1, n:1}
"silent" → {l:1, i:1, s:1, t:1, e:1, n:1} ← iguais ⇒ anagramas
É o mesmo hash map da seção Array, com uma pergunta diferente: em vez de "já vi este valor?", perguntamos "quantas vezes vi cada caractere?". Duas strings são anagramas se, e somente se, têm a mesma assinatura.
Os sinais no enunciado
- A palavra "anagrama" aparece literalmente.
- "Reorganizar / permutar os caracteres de...".
- "Agrupar palavras que são rearranjos umas das outras".
- Qualquer coisa em que a ordem não importa, só a composição.
Duas formas da assinatura
- Mapa de contagens (
{char: quantidade}): geral, serve para qualquer alfabeto (Unicode inclusive). - String ordenada (
sorted("listen") == "eilnst"): mais simples de escrever, mas custa O(k log k) por palavra (k = tamanho). Útil como chave ao agrupar.
Exemplo 1 — Valid Anagram
"s e t são anagramas?"
- Força bruta: testar todas as permutações de
s— O(k!). Inviável. - O desperdício: permutar é absurdo quando só precisamos saber se a composição é a mesma.
- O padrão: compare as assinaturas de frequência. Uma forma elegante numa
passada só: conte +1 para cada char de
se −1 para cada char det; no fim, todas as contagens têm que ser zero.
Por que é O(n)? (justificando)
- A verificação de tamanho corta na hora os casos triviais.
- Duas passadas (uma por string), cada uma O(n), com operações de mapa O(1) por caractere → O(n) de tempo.
- O mapa guarda no máximo o número de caracteres distintos do alfabeto — para letras minúsculas, no máximo 26. Espaço O(1) (constante, não cresce com n).
Compare com a abordagem "ordenar e comparar": sorted(s) == sorted(t). Custa
O(n log n) — correta e curtíssima, mas mais lenta. Trade-off clássico:
simplicidade de código contra velocidade.
| Solução | Tempo | Espaço |
|---|---|---|
| Testar permutações | O(k!) | — |
| Ordenar e comparar | O(n log n) | O(n) |
| Mapa de frequência | O(n) | O(1) (alfabeto fixo) |
Exemplo 2 — Group Anagrams
"Agrupe as palavras que são anagramas entre si." Ex.: ["eat","tea","tan", "ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]].
- O desperdício: comparar cada palavra com todas as outras é O(n²) comparações de strings.
- O padrão: se anagramas têm a mesma assinatura, use a assinatura como chave de um hash map e jogue cada palavra no seu balde. Uma passada agrupa tudo.
A assinatura aqui costuma ser a string ordenada ("eat" → "aet"), porque
ela vira uma chave de dicionário naturalmente:
Por que é O(n · k log k)?
São n palavras; para cada uma, ordenar a assinatura custa O(k log k)
(k = tamanho da palavra). A inserção no hash map é O(k) (calcular o hash da
chave). Total: O(n · k log k). Muito melhor que comparar todos os pares
(O(n² · k)). Se quiser cravar O(n · k), troque a assinatura ordenada por uma
contagem de 26 posições transformada em chave — mesma ideia, sem o log.
Onde mais esse padrão aparece
A assinatura de frequência é a base do sliding window com contagens da próxima aula (a "janela válida" é definida por um critério sobre as frequências dentro dela) e reaparece em problemas de "permutação/substring que contém exatamente estes caracteres".
🧠 Quiz de fixação
0/41. Por que comparar frequências de caracteres identifica anagramas, mas comparar a ordem não?
2. No Valid Anagram, por que o truque de +1 para s e −1 para t funciona em uma passada?
3. Para letras minúsculas (a–z), por que a contagem de frequência usa espaço O(1)?
4. No Group Anagrams, por que usar a 'string ordenada' como chave do hash map agrupa corretamente?
Resumo
- A assinatura de frequência é a identidade de uma string sem a ordem.
- Valid Anagram: compare assinaturas (ou +1/−1 numa passada) — O(n), espaço O(1) no alfabeto fixo.
- Group Anagrams: use a assinatura como chave de hash map para agrupar — O(n·k log k), muito melhor que comparar pares.
Próxima aula: a assinatura de frequência ganha movimento — sliding window com mapa de contagens.