Skip to article
ALGORITHMICSDSA / Hashing
DSAeasy7 min read

Valid Anagram

One tally instead of two — and the Unicode bug hiding in the obvious Go solution.


Two words are anagrams if one is a rearrangement of the other: same letters, same counts, different order.

isAnagram("anagram", "nagaram") // true
isAnagram("rat", "car") // false

The obvious way

Sort both and compare:

func isAnagram(s string, t string) bool {
a, b := []rune(s), []rune(t)
slices.Sort(a)
slices.Sort(b)
return string(a) == string(b)
}

Four lines, obviously correct, O(nlogn)O(n \log n). Genuinely fine — and it does more work than the question needs, because it produces a total ordering when all you asked for was whether the letter counts match.

Count instead of sort

Order is exactly what an anagram throws away, so never compute it. Count each letter in the first word, subtract each letter in the second, and check that everything lands on zero.

1 / 7
+ anagram
nagaram
a
+1
g
0
m
0
n
-1
r
0

Counted a up and n down. Some counts are non-zero, which is expected mid-pass. Only the state after the final index decides anything.

One map, not two — the subtraction does the comparison as it goes.

func isAnagram(s string, t string) bool {
exists := make(map[rune]int)
sRunes := []rune(s)
tRunes := []rune(t)
if len(s) != len(t) {
return false
}
for i := range s {
exists[sRunes[i]]++
exists[tRunes[i]]--
}
for _, v := range exists {
if v != 0 {
return false
}
}
return true
}

O(n)O(n) time, and O(k)O(k) space where kk is the alphabet size — 26 for lowercase English, not nn.

This passes LeetCode. It also panics on the follow-up question the problem itself asks.

Two bugs, and they are the same mistake

Ranging over the rune slice fixes that panic, and is still not enough:

if len(s) != len(t) { return false } // BYTE length

"abc" and "aé" are both three bytes and pass this guard, but hold three runes and two. The loop then reads tRunes[2], which does not exist, and panics again — so fixing only the range moves the crash rather than removing it.

Both lines are the same error twice: counting bytes where the algorithm means characters.

func isAnagram(s string, t string) bool {
sRunes, tRunes := []rune(s), []rune(t)
// Rune count, not byte count: "aé" is 3 bytes and 2 characters.
if len(sRunes) != len(tRunes) {
return false
}
exists := make(map[rune]int, len(sRunes))
for i := range sRunes {
exists[sRunes[i]]++
exists[tRunes[i]]--
}
for _, v := range exists {
if v != 0 {
return false
}
}
return true
}

The array version

For a fixed, small alphabet, skip the map entirely:

func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
var counts [26]int
for i := 0; i < len(s); i++ {
counts[s[i]-'a']++
counts[t[i]-'a']--
}
for _, n := range counts {
if n != 0 {
return false
}
}
return true
}

Same complexity, several times faster in practice: no hashing, no allocation, and 26 ints sit in a couple of cache lines. Indexing s[i] gives a byte here, which is correct precisely because the constraint guarantees one byte per character.

The catch is in the first word of that sentence — fixed. An uppercase letter or a space makes s[i]-'a' wrap around (byte arithmetic is unsigned) and the index lands far outside the array, which Go catches as a panic rather than the silent memory corruption you would get in C. Reach for it only when the constraints genuinely pin the alphabet.

When sorting is still the better answer

If you have to compare one word against many, sort each once and use the sorted string as a key:

groups := make(map[string][]string)
for _, word := range words {
r := []rune(word)
slices.Sort(r)
key := string(r)
groups[key] = append(groups[key], word)
}

That is the “group anagrams” problem, and counting does not generalise to it as neatly — a canonical key is exactly what sorting produces and a tally does not.