How do sorting and character counting compare as canonical forms for anagram detection?

## The shared idea: a canonical form Two sequences are anagrams when they contain the same characters with the same multiplicities — the same **multiset**, ignoring order. Direct multiset comparison is awkward, so both standard techniques do the same trick: map each input to a *canonical form*, a representative that is identical for all members of an equivalence class, then test the two forms for equality. Sorting and counting differ only in which canonical form they build. The worked setting here is a word game that must catch shuffled duplicate answers: a player submits a word, and the server must decide whether it is a rearrangement of one already accepted this round. ## Canonical form by sorting Sort the characters of each input and compare the sorted sequences. The forms are equal exactly when the multisets are equal, because sorting is a deterministic function of the multiset alone. - **Time:** O(L log L) for length L, dominated by the sort. This is not an implementation weakness — any sort that works by comparing elements is bounded below by Omega(L log L) comparisons in the worst case. Escaping it means not comparing at all, which is precisely what counting does. - **Space:** O(L) if you must preserve the original input, since you sort a copy; O(1) or O(log L) auxiliary if you are allowed to sort in place, depending on the sort. - **Advantages:** the form is a directly comparable, orderable value, which makes it a natural grouping key when you want to bucket many inputs by anagram class rather than compare two. It also makes no assumption whatsoever about the alphabet. ## Canonical form by counting Walk each input once, incrementing a tally per character, then compare the tallies. - **Time:** O(L) to build each tally, plus O(k) to compare them for an alphabet of size k. A common refinement builds the tally from the first input, decrements while scanning the second, and aborts the moment a count goes negative; combined with an up-front length check this makes the whole comparison O(L) with no O(k) sweep at the end. - **Space:** O(k) — the tally, not the input. For a small fixed alphabet that is a constant. - **The classic wrong answer:** "a 26-slot count array is *the* canonical form." It is *a* canonical form for exactly one input class: lowercase letters of a single 26-letter script. The slot index is usually derived by subtracting the code of the first letter, so a digit, a space, an uppercase letter or an accented letter maps to a negative or out-of-range slot — an out-of-bounds access if you are lucky, a silently corrupted tally if the slot happens to land inside the table. The general form is a tally keyed by character, which costs a constant factor more per character and works for any alphabet. This is where mainstream runtimes visibly disagree on what "a character" even is — some expose text as fixed-width code units, others as variable-width sequences, and a tally that assumes one model produces different answers under the other. The fix at this tier is to state which unit you are counting rather than to assume. ## Choosing between them | | Sorting | Counting | |---|---|---| | Time | O(L log L) | O(L) | | Extra space | O(L) copy, or in-place | O(k) tally | | Alphabet assumption | none | must match the real input set | | Good as a grouping key | directly | only if serialised in a fixed order | On long inputs counting wins clearly. On very short inputs the log factor is a small multiplier and constants dominate, so sorting can measure faster while being simpler to reason about — asymptotic superiority promises nothing at small L. If you need to group thousands of inputs into anagram classes, the sorted form is the more convenient key, because a tally must be serialised into a fixed, deterministic order before it can be used as one. ## The cheap check people forget If the two inputs have different lengths they cannot be anagrams. That is O(1) and rejects a large share of pairs before any O(L) work. It is also a correctness guard for the decrement-and-abort variant: without an equal-length precondition, "no count went negative" does not prove the multisets match — the second input could simply be shorter and use up only part of the tally. ## What interviewers listen for The complexity of each form stated correctly and attributed to the right cause; the alphabet assumption named without being prompted; the length check offered as a first move; and an honest "it depends on L and on whether I am comparing a pair or grouping many" rather than a reflexive "counting is always better".