Derusting logic #01: Group Anagrams

After years programming, I realized my logic was rusty. I had not stopped writing code. What changed was that, little by little, I started outsourcing parts of the reasoning I used to exercise alone.

I picked exercise 49. Group Anagrams on LeetCode. The task is to receive a list of strings and group anagrams together.

What we need to solve

Input:

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

Possible result:

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

Group order does not matter.

What is an anagram?

Take eat, tea, and ate. Each has a once, e once, and t once. Positions change; the count of each letter stays the same.

The algorithm must turn those words into a shared representation. If all three produce the same key, I can use that key in a map and place them in the same group. The first problem is creating that key.

My first answer was sorting

I started using the sorted string as the key:

eat → aet
tea → aet
ate → aet

All three produce aet.

Sort-based solution

That was the first solution that came to mind. I was not trying for the leanest implementation right away. I wanted a coherent solution and to understand where it could improve.

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
}

What happens in this code:

1. sortString(str) turns the string into bytes, sorts the characters, and returns a new string.
2. sortedStr := sortString(str) produces the key for that term.
3. mapping[sortedStr] = append(...) uses that key to accumulate anagrams in the same group.
4. For eat, tea, and ate, sortedStr is always aet.

The map starts looking like this:

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

I compute one key and add the word directly to the matching group. The map avoids comparing every string with every other.

Where is the cost of this approach?

To discover the key, I sort each string. If a string has k characters, that sort costs roughly O(k log k). Repeating for n strings, the dominant part is O(n × k log k).

Why drop the sort?

For eat, I sorted characters to reach aet. For tea, I sorted again to reach the same aet. Sorting works because it creates a shared representation. But the problem does not require sorting anything.

To know whether two strings are anagrams, it is enough to check whether they hold the same count of each letter.

That observation changes the solution

Instead of placing letters in the same order, I can count how many times each appears. In this exercise, inputs use lowercase letters from a to z. Each string can be represented by 26 counters.

tea and ate produce the same count. I do not need to rearrange any character. I just walk the string and count occurrences. For eat, the relevant part is:

a = 1
e = 1
t = 1

Counting solution

var key [26]uint8 creates 26 slots, one per letter from a to z. key[str[i]-'a']++ finds each character’s slot and increments the counter. Then groups[key] = append(groups[key], str) uses the frequency vector itself as the group key.

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
}

What changed in complexity?

• Sorting: O(k log k) per string and O(n × k log k) for n strings.
• Counting: O(k) per string and O(n × k) for n strings.

The improvement appeared when I realized sorting did work the problem never asked for. The main change is from O(k log k) to O(k) per string.

The first solution was not wrong

It solves the problem and, depending on context, could be enough. The habit I wanted to recover was to keep thinking after the code starts working. Find a solution, return to the problem, and ask: what work is my algorithm doing without needing to?

I am not doing these exercises because LeetCode represents all software engineering work, nor to chase the most sophisticated solution. I am doing them because I noticed that using AI every day reduced how often I insist on a problem alone. I want to reserve space to exercise that again: read, try, fail, review the approach, and only then compare paths.

---

Series Derusting logic #01 — Group Anagrams. Adapted from the original carousel; problem at leetcode.com/problems/group-anagrams.