Frequency and Anagram Counting

A surprising number of string problems reduce to one question: which characters, and how many of each? Order is irrelevant; only the multiset matters. Once you notice that, “is this an anagram”, “group the anagrams”, “find every anagram inside a longer string”, and “sort by frequency” all collapse into variations on a single CounterCounter.

The skill this page builds is choosing the right canonical key — a value that is identical for inputs that should be considered equivalent, and different for inputs that should not.

What you’ll learn

collections.Countercollections.Counter as the workhorse, and its two comparison idioms.
Canonical keys: sorted-tuple vs. count-tuple, and the real trade-off.
The sliding-window + counter combination, and the deldel-on-zero detail that makes dictionary comparison work.
Bijection checks (isomorphic strings, word patterns) — why one map is not enough.
Three real LeetCode problems solved in the browser: 242, 49, 438.

The cue

The core tool

counter_basics.py

from collections import Counter
 
c = Counter("mississippi")
print(c)                      # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
print(c["s"])                 # 4
print(c["z"])                 # 0  -- missing keys read as 0, no KeyError
 
# Comparison: two strings are anagrams iff their Counters are equal
print(Counter("listen") == Counter("silent"))     # True
 
# Containment: can "aab" be built from the letters of "baaxy"?
print(Counter("aab") <= Counter("baaxy"))         # True  (multiset subset)
 
print(c.most_common(2))       # [('i', 4), ('s', 4)]

counter_basics.py

from collections import Counter
 
c = Counter("mississippi")
print(c)                      # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
print(c["s"])                 # 4
print(c["z"])                 # 0  -- missing keys read as 0, no KeyError
 
# Comparison: two strings are anagrams iff their Counters are equal
print(Counter("listen") == Counter("silent"))     # True
 
# Containment: can "aab" be built from the letters of "baaxy"?
print(Counter("aab") <= Counter("baaxy"))         # True  (multiset subset)
 
print(c.most_common(2))       # [('i', 4), ('s', 4)]

Two idioms carry most of the weight: ==== for “same multiset” and <=<= for “can be built from”. The subset operator is genuinely useful and often forgotten — LC 383 is a one-liner with it.

Canonical keys

To group equivalent strings, map each to a key that is equal exactly when they are equivalent. Two standard choices:

canonical_keys.py

word = "eat"
 
key_sorted = tuple(sorted(word))          # ('a', 'e', 't')
print(key_sorted)
 
counts = [0] * 26                          # count-tuple, lowercase a-z only
for ch in word:
    counts[ord(ch) - ord("a")] += 1
key_counts = tuple(counts)
print(key_counts)                          # (1, 0, 0, 0, 1, 0, ..., 1, 0, 0)

canonical_keys.py

word = "eat"
 
key_sorted = tuple(sorted(word))          # ('a', 'e', 't')
print(key_sorted)
 
counts = [0] * 26                          # count-tuple, lowercase a-z only
for ch in word:
    counts[ord(ch) - ord("a")] += 1
key_counts = tuple(counts)
print(key_counts)                          # (1, 0, 0, 0, 1, 0, ..., 1, 0, 0)

Key	Cost per word	Works for	Notes
`tuple(sorted(w))tuple(sorted(w))`	$O(L \log L)$	any alphabet	Short, obvious, usually fast enough
26-slot count tuple	$O(L)$	fixed small alphabet	Asymptotically better; verbose

With $L$ the word length and $k$ words: sorting keys gives $O(k \cdot L \log L)$ , count tuples give $O(k \cdot L)$ . For interview-scale inputs the sorted key is almost always the right call — write it, then mention the count-tuple as the optimisation. Reaching for the verbose one first, unimprompted, tends to read as premature optimisation.

The variant map

Variant	The key idea	Canonical problem
Same multiset?	`Counter(a) == Counter(b)Counter(a) == Counter(b)`	242 Valid Anagram
Group by multiset	Canonical key into a `defaultdict(list)defaultdict(list)`	49 Group Anagrams
Buildable from?	`Counter(need) <= Counter(have)Counter(need) <= Counter(have)`	383 Ransom Note
Find all anagram windows	Fixed-size window + counter comparison	438 · 567
Order by frequency	`Counter.most_common()Counter.most_common()`, or bucket by count	451 · 347
First unique	Count in pass 1, scan for count `== 1== 1` in pass 2	387
Consistent bijection	Two maps, one per direction	205 · 290
Counts match but letters may be remapped	Compare the sorted multiset of counts	1657

Practice — real LeetCode problems

LC 242 — Valid Anagram · Easy

Problem. Given two strings ss and tt, return TrueTrue if tt is an anagram of ss — that is, a rearrangement using exactly the same letters with the same counts.

Constraints. 1 <= len(s), len(t) <= 5 * 10^41 <= len(s), len(t) <= 5 * 10^4, lowercase English letters.

Examples. ("anagram", "nagaram")("anagram", "nagaram") gives TrueTrue · ("rat", "car")("rat", "car") gives FalseFalse · ("a", "ab")("a", "ab") gives FalseFalse

Editorial — approach, complexity, follow-ups

Two strings are anagrams exactly when their character multisets are equal. CounterCounter builds those multisets in one pass each and compares them.

Time $O(n)$ . Space $O(|\Sigma|)$ — bounded by the alphabet, so $O(1)$ for lowercase English.

The length check is not strictly required (unequal lengths give unequal counters) but it is a free $O(1)$ rejection, and stating it shows you think about cheap exits before expensive work.

sorted(s) == sorted(t)sorted(s) == sorted(t) is a perfectly acceptable one-line alternative at $O(n \log n)$ time and $O(n)$ space. Say both, note the trade, pick the counter.

Follow-ups you should expect: “What if the input is Unicode?” — the CounterCounter already handles it; only the space bound changes from $O(1)$ to $O(\min(n, |\Sigma|))$ . Worth adding that “anagram” gets genuinely murky with combining characters and case folding, so you would normalise (e.g. NFC) first. “Do it with $O(1)$ space for lowercase input?” — a 26-slot list, incrementing for ss and decrementing for tt, then check all zeros. “Group many strings by anagram class?” — that is LC 49, next.

LC 49 — Group Anagrams · Medium

Problem. Given an array of strings, group together all strings that are anagrams of one another. Return the groups in any order.

Constraints. 1 <= len(strs) <= 10^41 <= len(strs) <= 10^4, 0 <= len(strs[i]) <= 1000 <= len(strs[i]) <= 100, lowercase English letters.

Examples. ["eat","tea","tan","ate","nat","bat"]["eat","tea","tan","ate","nat","bat"] gives [["eat","tea","ate"],["tan","nat"],["bat"]][["eat","tea","ate"],["tan","nat"],["bat"]] · [""][""] gives [[""]][[""]]

Editorial — approach, complexity, follow-ups

Anagram classes are equivalence classes. Compute a representative (canonical key) for each word and bucket by it.

Time $O(k \cdot L \log L)$ for kk words of length up to LL. Space $O(k \cdot L)$ .

With the 26-slot count tuple as the key, this drops to $O(k \cdot L)$ :

python

key = [0] * 26
for ch in w:
    key[ord(ch) - ord("a")] += 1
groups[tuple(key)].append(w)

python

key = [0] * 26
for ch in w:
    key[ord(ch) - ord("a")] += 1
groups[tuple(key)].append(w)

Worth mentioning; usually not worth writing first. The sorted key is shorter, obviously correct, and fast for L <= 100L <= 100. Note also that the count-tuple version assumes lowercase ASCII, so it is less general — if the interviewer widens the alphabet, the sorted key still works unchanged.

Follow-ups you should expect: “Groups in a specific order?” — sort the result, or use a plain dictdict (insertion-ordered since Python 3.7) to keep first-appearance order. “What if the strings are enormous?” — the count tuple avoids the log Llog L. “Memory is tight?” — you must hold all groups to answer, so $O(k \cdot L)$ is a lower bound; you could stream out groups if input arrived pre-sorted by key. “Case-insensitive or with spaces?” — normalise before keying, and ask whether they count.

LC 438 — Find All Anagrams in a String · Medium

Problem. Given strings ss and pp, return the start indices of all substrings of ss that are anagrams of pp, in ascending order.

Constraints. 1 <= len(s), len(p) <= 3 * 10^41 <= len(s), len(p) <= 3 * 10^4, lowercase English letters.

Examples. s = "cbaebabacd", p = "abc"s = "cbaebabacd", p = "abc" gives [0,6][0,6] · s = "abab", p = "ab"s = "abab", p = "ab" gives [0,1,2][0,1,2] · s = "af", p = "be"s = "af", p = "be" gives [][]

Editorial — approach, complexity, follow-ups

An anagram of pp has exactly len(p)len(p) characters, so every candidate is a fixed-width window. Build the counter once, then maintain it in $O(1)$ per step: one increment for the entering character, one decrement for the leaving one.

Time $O(n)$ . Space $O(|\Sigma|) = O(1)$ for lowercase English.

Comparing whole dicts is $O(|\Sigma|)$ , so strictly the loop is $O(n \cdot |\Sigma|)$ . For a tighter version, maintain a single matchesmatches counter tracking how many characters currently have the right count, and compare it against the number of distinct characters in pp — that makes each step genuinely $O(1)$ . Worth mentioning as the optimisation.

Follow-ups you should expect: “Just return whether one exists (LC 567)?” — same window, return TrueTrue on the first match. “Return the substrings instead of indices?” — slice at each hit. “Make each step truly $O(1)$ ?” — the matchesmatches-counter refinement above. “Unicode alphabet?” — space becomes $O(\min(n, |\Sigma|))$ and the dict-comparison cost grows, which is a stronger argument for the matchesmatches counter.

LeetCode problem set

#	Problem	Difficulty	The twist
242	Valid Anagram	Easy	`Counter(s) == Counter(t)Counter(s) == Counter(t)` after a length check
383	Ransom Note	Easy	Multiset containment — `Counter(note) <= Counter(magazine)Counter(note) <= Counter(magazine)`
387	First Unique Character in a String	Easy	Count in pass 1, then scan in order for the first count of 1
205	Isomorphic Strings	Easy	Two maps, one per direction — one is not enough
290	Word Pattern	Easy	205 over words instead of characters; check the lengths match
49	Group Anagrams	Medium	Canonical key into a `defaultdict(list)defaultdict(list)`
438	Find All Anagrams in a String	Medium	Fixed window + counter; delete zero-count keys
451	Sort Characters By Frequency	Medium	`most_common()most_common()`, or bucket by count for $O(n)$
1657	Determine if Two Strings Are Close	Medium	Same character set, and the same sorted multiset of counts

Interview follow-ups

They ask	What they’re checking	The answer
“Counter vs. sorting?”	Complexity awareness	$O(n)$ and $O(1)$ space vs. $O(n \log n)$ and $O(n)$ ; both fine, know which you chose
“Why can’t a `CounterCounter` be the dict key?”	Python fluency	It is mutable and therefore unhashable — freeze it into a tuple
“Unicode input?”	Generality	The dict handles it; the $O(1)$ space claim becomes $O(\min(n, \\|\Sigma\\|))$ , and normalisation/case-folding become real questions
“Make the window step truly $O(1)$ ”	Depth	Track a `matchesmatches` count of how many characters have the correct frequency instead of comparing whole maps
“Why two maps for isomorphic strings?”	Rigour	One direction permits two characters mapping onto the same image, which is not a bijection
“Sort by frequency in $O(n)$ ”	Beyond the obvious	Bucket sort by count — counts are bounded by `nn`, so no comparison sort is needed

Edge-case checklist

Different lengths — an instant FalseFalse for anagram checks; for LC 290 an explicit length check is required.
Empty string — an anagram of itself; make sure Counter("")Counter("") paths work.
pp longer than ss (LC 438) — return [][] before building a window you cannot fill.
Every window matches — ("abab", "ab")("abab", "ab") gives [0,1,2][0,1,2], so overlaps count.
Counts reaching zero — delete the key, or rely knowingly on CounterCounter equality semantics.
Repeated characters in the pattern — ("baa", "aa")("baa", "aa"); a set-based (rather than multiset-based) solution fails here.
Single character inputs — the smallest window case.
Case and whitespace — unspecified in most of these problems; ask rather than assume.

Recap

When order does not matter, discard it and keep the multiset — that reduction is the pattern.
CounterCounter gives you ==== for “same multiset” and <=<= for “can be built from”; both are worth having at your fingertips.
To group equivalents, pick a canonical key: tuple(sorted(w))tuple(sorted(w)) is the default, and a 26-slot count tuple is the $O(L)$ upgrade. The key must be hashable, which is why it is a tuple and not a CounterCounter.
Fixed-width anagram search is a sliding window plus a counter; delete zero-count keys so the comparison holds.
Bijections need two maps, one per direction.
The deeper skill is asking what do the allowed operations preserve? — which is what turns LC 1657 from a puzzle into two lines.

Next: Palindrome Patterns — expand-around-centre, the two-pointer check, and where palindromes become a DP problem instead.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Frequency and Anagram Counting

What you’ll learn

The cue

The core tool

Canonical keys

The variant map

Practice — real LeetCode problems

LC 242 — Valid Anagram · Easy

LC 49 — Group Anagrams · Medium

LC 438 — Find All Anagrams in a String · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?