Desenferrujando a lógica #01: Group Anagrams

Depois de anos programando, percebi que minha lógica estava enferrujada. Eu não tinha parado de escrever código. O que mudou foi que, aos poucos, comecei a terceirizar partes do raciocínio que antes precisava exercitar sozinho.

Escolhi o exercício 49. Group Anagrams no LeetCode. A proposta é receber uma lista de strings e reunir os anagramas no mesmo grupo.

O que precisamos resolver

Entrada:

["eat", "tea", "tan", "ate", "nat", "bat"]

Resultado possível:

["eat", "tea", "ate"]
["tan", "nat"]
["bat"]

A ordem dos grupos não importa.

O que é um anagrama?

Pegue eat, tea e ate. Cada uma tem a uma vez, e uma vez e t uma vez. A posição muda; a quantidade de cada letra continua igual.

O algoritmo precisa transformar essas palavras em uma representação comum. Se as três produzirem a mesma chave, posso usar essa chave em um map e colocá-las no mesmo grupo. O primeiro problema é criar essa chave.

Minha primeira resposta foi ordenar

Comecei usando a string ordenada como chave:

eat → aet
tea → aet
ate → aet

As três produzem aet.

Solução usando sort

Essa foi a primeira solução que me ocorreu. Eu não estava tentando a implementação mais enxuta de imediato. Queria montar uma solução coerente e entender onde ela poderia melhorar.

func sortString(str string) string {
	b := []byte(str)
	slices.Sort(b)
	return string(b)
}

func groupAnagrams(strs []string) [][]string {
	mapping := make(map[string][]string)

	for _, str := range strs {
		sortedStr := sortString(str)
		mapping[sortedStr] = append(mapping[sortedStr], str)
	}

	result := make([][]string, 0, len(mapping))

	for _, group := range mapping {
		result = append(result, group)
	}

	return result
}

O que acontece nesse código:

1. sortString(str) transforma a string em bytes, ordena os caracteres e devolve uma nova string.
2. sortedStr := sortString(str) produz a chave daquele termo.
3. mapping[sortedStr] = append(...) usa essa chave para acumular os anagramas no mesmo grupo.
4. Para eat, tea e ate, sortedStr será sempre aet.

O mapa começa a ficar assim:

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

Calculo uma chave e adiciono a palavra diretamente ao grupo correspondente. O map evita comparar cada string com todas as outras.

Onde está o custo dessa abordagem?

Para descobrir a chave, preciso ordenar cada string. Se uma string tem k caracteres, essa ordenação custa aproximadamente O(k log k). Repetindo para n strings, a parte dominante fica em O(n × k log k).

Por que retirar o sort?

Para eat, eu ordenava os caracteres para chegar em aet. Para tea, fazia outra ordenação para chegar no mesmo aet. O sort funciona porque cria uma representação comum. Só que o problema não exige ordenar nada.

Para saber se duas strings são anagramas, basta verificar se possuem a mesma quantidade de cada letra.

Essa observação muda a solução

Em vez de colocar as letras na mesma ordem, posso contar quantas vezes cada uma aparece. Nesse exercício, as entradas usam letras minúsculas de a até z. Cada string pode ser representada por 26 contadores.

tea e ate produzem a mesma contagem. Não preciso reorganizar nenhum caractere. Só percorro a string e conto as ocorrências. Para eat, a parte relevante fica:

a = 1
e = 1
t = 1

Solução usando contagem

var key [26]uint8 cria 26 posições, uma para cada letra de a até z. key[str[i]-'a']++ encontra a posição de cada caractere e incrementa o contador. Depois, groups[key] = append(groups[key], str) usa o próprio vetor de frequências como chave do grupo.

func groupAnagrams(strs []string) [][]string {
	groups := make(map[[26]uint8][]string, len(strs))

	for _, str := range strs {
		var key [26]uint8

		for i := 0; i < len(str); i++ {
			key[str[i]-'a']++
		}

		groups[key] = append(groups[key], str)
	}

	result := make([][]string, 0, len(groups))

	for _, group := range groups {
		result = append(result, group)
	}

	return result
}

O que mudou em complexidade?

• Ordenação: O(k log k) por string e O(n × k log k) para n strings.
• Contagem: O(k) por string e O(n × k) para n strings.

A melhoria apareceu quando percebi que a ordenação fazia um trabalho que o problema não exigia. A mudança principal é de O(k log k) para O(k) por string.

A primeira solução não estava errada

Ela resolve o problema e, dependendo do contexto, poderia ser suficiente. O hábito que eu queria recuperar era continuar pensando depois que o código começa a funcionar. Encontrar uma solução, voltar ao problema e perguntar: que trabalho meu algoritmo está fazendo sem precisar?

Não estou fazendo esses exercícios porque LeetCode representa todo o trabalho de engenharia de software, nem para disputar a solução mais sofisticada. Estou fazendo porque percebi que usar IA todos os dias reduziu a quantidade de vezes em que preciso insistir sozinho em um problema. Quero reservar espaço para exercitar isso novamente: ler, tentar, errar, revisar a abordagem e só depois comparar caminhos.

---

Série Desenferrujando a lógica #01 — Group Anagrams. Adaptado do carousel autoral; problema em leetcode.com/problems/group-anagrams.