Strings and frequency maps

A word-game server checks whether a player has enough letters to form a proposed word. Finding an a in the available pool doesn't establish that the word can be formed: it may need three copies and the pool may contain only one.

The game compares normalized letters, ignoring case and punctuation. Recounting the pool for each requested symbol works, but frequency maps can count both strings once and report exactly what is missing.

Checking the available letters

A map records multiplicity; a set only records presence. A rune is a Unicode code point, while indexing a string gives a byte. Case folding can expand one code point into several, so normalization must precede counting. Canonical normalization and grapheme segmentation are separate choices.

Counting the missing copies

After the lesson's text-normalization policy, available aab and requested baaac give counts of two versus three for a, one versus one for b, and zero versus one for c. The shortage is therefore one a and one c. A set would notice the missing c but lose the extra a; the relevant information is quantity, not membership.

counts := map[rune]int{}
counts['é']++
fmt.Println(counts['é'], counts['x']) // 1 0

When order starts to matter

Map lookup for a missing key returns the element type's zero value. This suits counters, but cannot distinguish missing from a stored zero unless you use the comma-ok form. Count both texts once for expected O(L) counting work and O(u) distinct-symbol memory; rescanning for each distinct rune costs O(uL). Missing extra copies matter in inventory reconciliation and anagram checks. Counts lose sequence information and cannot answer contiguous substring queries.

Let L be the normalized text length and u the number of distinct letters. Recounting for every letter costs O(uL). Two count maps reduce that to expected O(L) counting work, with O(u log u) for sorted output keys and O(u) count storage. This does not recover the original letter order.

The response needs quantities for missing letters, including letters already present in insufficient numbers. A set of absent symbols cannot express that.