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

Find missing letter multiplicities, rather than merely checking whether each letter occurs. Requested "aaa" and loaded "ab" require two more a values even though a is present.

A set loses counts. Repeatedly counting a whole string for each requested letter preserves meaning but repeats work. Build frequency maps only after applying the complete-string normalization rule, then subtract and retain positive deficits.

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.

A set records existence; a frequency map records multiplicity. Deficits must subtract counts before dropping zero or negative values. Normalize whole strings before iterating code points because case conversion may expand characters. Final target: O(n+m+k log k), including sorted output, with O(k) counts.

Case conversion can expand a character before code-point counting. This Java normalization deliberately specifies both transformations:

import java.util.*;

class Example {
    public static void main(String[] args) {
        String original = "ß";
        String normalized = original.toUpperCase(Locale.ROOT).toLowerCase(Locale.ROOT);
        assert original.codePointCount(0, original.length()) == 1;
        assert normalized.equals("ss");
        assert normalized.codePointCount(0, normalized.length()) == 2;
    }
}

Counting before normalization would see one letter instead of two. Locale.ROOT avoids dependence on the machine locale; the documented two-step conversion is still a Java-specific normalization rule, not a promise of universal Unicode casefold equivalence.

When order starts to matter

Multiset subtraction is useful for resource deficits, required symbol inventories, and reconciliation of repeated values. Decide normalization and output ordering at the boundary so different producers cannot silently disagree about identity.

Normalize each string with toUpperCase(Locale.ROOT).toLowerCase(Locale.ROOT), then count only code points for which Character.isLetter is true. Return positive requested-minus-loaded deficits in ascending code-point key order, with each key a one-code-point String. This explicit Java normalization folds ß to ss; it is not a universal Unicode casefold operation. Do not otherwise normalize. Empty strings are valid. ("ab","aaa") gives {a=2}.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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