Desenoxidando la lógica #01: Group Anagrams

Después de años programando, percibí que mi lógica estaba oxidada. Yo no había dejado de escribir código. Lo que cambió fue que, poco a poco, empecé a tercerizar partes del razonamiento que antes necesitaba ejercitar solo.

Elegí el ejercicio 49. Group Anagrams en LeetCode. La propuesta es recibir una lista de strings y reunir los anagramas en el mismo grupo.

Lo que necesitamos resolver

Entrada:

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

Resultado posible:

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

El orden de los grupos no importa.

¿Qué es un anagrama?

Toma eat, tea y ate. Cada una tiene a una vez, e una vez y t una vez. La posición cambia; la cantidad de cada letra sigue igual.

El algoritmo necesita transformar esas palabras en una representación común. Si las tres producen la misma clave, puedo usar esa clave en un map y colocarlas en el mismo grupo. El primer problema es crear esa clave.

Mi primera respuesta fue ordenar

Empecé usando el string ordenado como clave:

eat → aet
tea → aet
ate → aet

Las tres producen aet.

Solución usando sort

Esta fue la primera solución que se me ocurrió. No intentaba la implementación más concisa de inmediato. Quería montar una solución coherente y entender dónde podría mejorar.

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
}

Lo que ocurre en ese código:

1. sortString(str) transforma el string en bytes, ordena los caracteres y devuelve un nuevo string.
2. sortedStr := sortString(str) produce la clave de aquel término.
3. mapping[sortedStr] = append(...) usa esa clave para acumular los anagramas en el mismo grupo.
4. Para eat, tea y ate, sortedStr será siempre aet.

El mapa empieza a quedar así:

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

Calculo una clave y añado la palabra directamente al grupo correspondiente. El map evita comparar cada string con todas las demás.

¿Dónde está el costo de ese enfoque?

Para descubrir la clave, necesito ordenar cada string. Si un string tiene k caracteres, esa ordenación cuesta aproximadamente O(k log k). Repitiendo para n strings, la parte dominante queda en O(n × k log k).

¿Por qué quitar el sort?

Para eat, ordenaba los caracteres para llegar a aet. Para tea, hacía otra ordenación para llegar al mismo aet. El sort funciona porque crea una representación común. Solo que el problema no exige ordenar nada.

Para saber si dos strings son anagramas, basta verificar si poseen la misma cantidad de cada letra.

Esa observación cambia la solución

En lugar de colocar las letras en el mismo orden, puedo contar cuántas veces aparece cada una. En este ejercicio, las entradas usan letras minúsculas de a a z. Cada string puede representarse por 26 contadores.

tea y ate producen el mismo conteo. No necesito reorganizar ningún carácter. Solo recorro el string y cuento las ocurrencias. Para eat, la parte relevante queda:

a = 1
e = 1
t = 1

Solución usando conteo

var key [26]uint8 crea 26 posiciones, una para cada letra de a a z. key[str[i]-'a']++ encuentra la posición de cada carácter e incrementa el contador. Después, groups[key] = append(groups[key], str) usa el propio vector de frecuencias como clave del 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
}

¿Qué cambió en complejidad?

• Ordenación: O(k log k) por string y O(n × k log k) para n strings.
• Conteo: O(k) por string y O(n × k) para n strings.

La mejora apareció cuando percibí que la ordenación hacía un trabajo que el problema no exigía. El cambio principal es de O(k log k) a O(k) por string.

La primera solución no estaba equivocada

Resuelve el problema y, según el contexto, podría bastar. El hábito que quería recuperar era seguir pensando después de que el código empieza a funcionar. Encontrar una solución, volver al problema y preguntar: ¿qué trabajo está haciendo mi algoritmo sin necesitarlo?

No hago estos ejercicios porque LeetCode represente todo el trabajo de ingeniería de software, ni para disputar la solución más sofisticada. Los hago porque percibí que usar IA todos los días redujo la cantidad de veces en que necesito insistir solo en un problema. Quiero reservar espacio para ejercitarlo de nuevo: leer, intentar, errar, revisar el enfoque y solo después comparar caminos.

---

Serie Desenoxidando la lógica #01 — Group Anagrams. Adaptado del carrusel autoral; problema en leetcode.com/problems/group-anagrams.