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

Multiplicity requires counts, rather than a set. The normalization order matters: casefold the whole string, then retain alphabetic code points. U+00DF expands to two s code points; counting original characters first loses that information. Canonical Unicode normalization is a separate policy and is deliberately absent.

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.

Text text = U"éÉß"; // four folded letters: é, é, s, s
std::map<char32_t, Int> counts;
// Increment each code point after unicode_casefold(text) and unicode_isalpha(c).

When order starts to matter

C++ std::tolower does not implement full Unicode case folding. A byte of UTF-8 is also not a character, and passing a negative signed char to cctype functions is invalid. This lesson provides unicode.hpp with Unicode casefold and alphabetic tables generated for the documented Unicode version. Those helpers are infrastructure, not the frequency-map solution. Text stores code points, so expansions and sorted result keys remain explicit. A map sorts keys; an unordered map would require a separate sorted emission step. Final counting costs O(L log U) with ordered maps, or expected O(L) plus O(U log U) result ordering with hash maps.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged. Text ordering follows Unicode code points (Text) or the documented UTF-8 identifier order (std::string).

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