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

The prototype can identify each requested letter and repeatedly scan both normalized strings for its count. Building one count map per input avoids those repeated scans. Map lookup/update is treated as expected constant time in the usual hash-table analysis; output ordering is a separate step.

Counting the missing copies

Use the supplied normalizeLetters(text) helper from exercise.mjs. It performs full case folding, including expansions, then filters to alphabetic code points. toLowerCase() alone is insufficient: ß folds to ss. Case folding is also different from canonical normalization, which this exercise does not apply.

For loaded "Aab!" and requested "baaac", normalized counts are a:2/b:1 and a:3/b:1/c:1. The positive deficits are a:1/c:1. A set difference would lose the extra missing a.

The output is an object whose property insertion order is ascending Unicode code-point order. Map insertion order reflects processing order, not alphabetic order. Each result key is one alphabetic code point, so comparing key.codePointAt(0) supplies the required order; localeCompare and default UTF-16 sorting are different policies. Count after folding because one source code point may expand to several counted letters.

import { normalizeLetters } from "./exercise.mjs";
const letters = normalizeLetters("Straße!");
console.log(letters.join("")); // strasse
const counts = new Map();
counts.set("a", (counts.get("a") ?? 0) + 1);
console.log(counts.get("a")); // 1

When order starts to matter

For total normalized length L and u distinct letters, rescanning costs O(uL). Count maps plus sorted emission take expected O(L + u log u) time and O(u) map space, apart from normalized input storage. Frequency maps cannot recover order, contiguous matches or grapheme boundaries. A fixed small alphabet may fit a counter array; general Unicode text needs an explicit code-point policy.

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