Pattern 1: Character counting (anagrams)

Two words are anagrams when they have exactly the same characters, in any order. The tool that captures this is the frequency map — a string's "fingerprint" that ignores order.

Tried it? Comparing all permutations is O(k!) — infeasible. Sorting the two strings and comparing works (O(k log k)), but there's something even more direct. The theory below shows the "signature" that identifies anagrams in O(n).

The theory: the frequency signature

How do you tell whether "listen" and "silent" are the same thing rearranged? Comparing order doesn't help — order is exactly what changes. What doesn't change is how many times each letter appears. That count vector is the signature:

"listen" → {l:1, i:1, s:1, t:1, e:1, n:1}
"silent" → {l:1, i:1, s:1, t:1, e:1, n:1}   ← equal ⇒ anagrams

It's the same hash map from the Array section, with a different question: instead of "have I seen this value?", we ask "how many times have I seen each character?". Two strings are anagrams if and only if they have the same signature.

The signs in the prompt

• The word "anagram" appears literally.
• "Rearrange / permute the characters of...".
• "Group words that are rearrangements of one another".
• Anything where order doesn't matter, only the composition.

Two forms of the signature

• Count map ({char: amount}): general, works for any alphabet (Unicode included).
• Sorted string (sorted("listen") == "eilnst"): simpler to write, but costs O(k log k) per word (k = length). Useful as a key when grouping.

Example 1 — Valid Anagram

"Are s and t anagrams?"

• Brute force: test all permutations of s — O(k!). Infeasible.
• The waste: permuting is absurd when all we need to know is whether the composition is the same.
• The pattern: compare the frequency signatures. An elegant way in a single pass: count +1 for each char of s and −1 for each char of t; at the end, all the counts must be zero.

Why is it O(n)? (justifying)

• The length check immediately rules out trivial cases.
• Two passes (one per string), each O(n), with O(1) map operations per character → O(n) time.
• The map holds at most the number of distinct characters of the alphabet — for lowercase letters, at most 26. O(1) space (constant, doesn't grow with n).

Compare this with the "sort and compare" approach: sorted(s) == sorted(t). It costs O(n log n) — correct and very short, but slower. A classic trade-off: code simplicity against speed.

Example 2 — Group Anagrams

"Group the words that are anagrams of one another." E.g.: ["eat","tea","tan", "ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]].

• The waste: comparing each word with all the others is O(n²) string comparisons.
• The pattern: if anagrams have the same signature, use the signature as the key of a hash map and drop each word into its bucket. One pass groups everything.

The signature here is usually the sorted string ("eat" → "aet"), because it naturally becomes a dictionary key:

Why is it O(n · k log k)?

There are n words; for each one, sorting the signature costs O(k log k) (k = word length). Inserting into the hash map is O(k) (computing the key's hash). Total: O(n · k log k). Much better than comparing all pairs (O(n² · k)). If you want to nail O(n · k), swap the sorted signature for a 26-slot count turned into a key — same idea, without the log.

Where else this pattern shows up

The frequency signature is the basis of the sliding window with counts in the next lesson (the "valid window" is defined by a criterion over the frequencies inside it) and reappears in problems about "a permutation/substring that contains exactly these characters".

Summary

• The frequency signature is a string's identity without order.
• Valid Anagram: compare signatures (or +1/−1 in a single pass) — O(n), O(1) space on a fixed alphabet.
• Group Anagrams: use the signature as a hash map key to group — O(n·k log k), much better than comparing pairs.

Next lesson: the frequency signature gets some motion — sliding window with a count map.