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 Counter.

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.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 del-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

You are looking at frequency counting when…

• The word “anagram”, “permutation”, “rearrange”, or “reorder” appears — 242, 49, 438, 567.
• The question is “can X be built from Y” — 383 Ransom Note.
• You need counts of things: most frequent, first unique, top-k — 387, 451, 347.
• Two strings must have a consistent one-to-one character mapping — 205, 290.
• Order explicitly does not matter. That phrase is the giveaway: it means you may throw away order and keep only the multiset.

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)]

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.

Counter equality and zero counts

Counter equality ignores keys whose count is zero, so Counter(a=1, b=0) == Counter(a=1) is True. That is convenient here — but a plain dict does not behave that way, and {'a': 1, 'b': 0} != {'a': 1}.

This matters in sliding-window problems where you decrement counts: if you are comparing plain dicts you must del a key when it hits zero. With Counter, decrementing to zero leaves the key present but equality still works. Mixing the two mental models is a classic source of “why doesn’t my window match” bugs.

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)

Key	Cost per word	Works for	Notes
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.

A Counter cannot be a dict key

Counter and dict are unhashable, so groups[Counter(w)].append(w) raises TypeError. That is precisely why the canonical key is a tuple. If you want a counter-shaped key, freeze it: tuple(sorted(Counter(w).items())).

Visual intuition

An anagram is a multiset, not an ordering — so “is this window an anagram” is really “do these two frequency maps agree”. The chips are those maps.

arrayTwo frequency maps, compared once per stepLC 438 · O(n) time, O(1) space

c0b1a2e3b4a5b6a7c8d9

a0/1b0/1c0/1

1def find_anagrams(s, p):2    need = Counter(p)3    window = Counter()4    out, k = [], len(p)5    for i, ch in enumerate(s):6        window[ch] += 17        if i >= k:8            left = s[i - k]9            window[left] -= 110            if window[left] == 0: del window[left]   # keep maps comparable11        if window == need:12            out.append(i - k + 1)13    return out

patternabck3

setupAn anagram is a multiset, not an ordering — so the question "is this window an anagram of the pattern" is really "do these two frequency maps match". A fixed-width window of 3 slides once across the string, and each step changes exactly two counts.

Play‹›1/20⟲

Watch the delete when a count reaches zero. In Python a Counter carrying an extra zero-valued key is NOT equal to one without it, so skipping that delete makes the comparison silently fail — one of the nastiest bugs in this pattern because the logic looks right.

Complexity

Approach	Time	Space
Sort every window and compare strings	$O(n \cdot k \log k)$	$O(k)$
Rebuild the window counter each step	$O(n \cdot k)$	$O(1)$
Slide the counter, compare maps	$O(n)$	$O(1)$

The $O(1)$ space is worth defending out loud: the map holds at most 26 keys for lowercase input, and 26 is a constant. Comparing two whole maps is likewise $O(26) = O(1)$, which is what keeps the scan linear rather than $O(26n)$ — and if the alphabet were unbounded, that claim would not hold.

The variant map

Variant	The key idea	Canonical problem
Same multiset?	Counter(a) == Counter(b)	242 Valid Anagram
Group by multiset	Canonical key into a defaultdict(list)	49 Group Anagrams
Buildable from?	Counter(need) <= Counter(have)	383 Ransom Note
Find all anagram windows	Fixed-size window + counter comparison	438 · 567
Order by frequency	Counter.most_common(), or bucket by count	451 · 347
First unique	Count in pass 1, scan for count == 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

Bijection checks need two maps

For “isomorphic strings”, a single s -> t map is not enough. On s = "badc", t = "baba", mapping d -> a and c -> b looks consistent one way, but a is then the image of both a and d — not a bijection. Maintain both s -> t and t -> s and reject on either conflict.

Practice — real LeetCode problems

LC 242 — Valid Anagram · Easy

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

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

Examples. ("anagram", "nagaram") gives True · ("rat", "car") gives False · ("a", "ab") gives False

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Two strings are anagrams exactly when their character multisets are equal. Counter 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) 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 Counter 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 s and decrementing for t, 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^4, 0 <= len(strs[i]) <= 100, lowercase English letters.

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

pch.exerciseTag pch.exerciseTitle

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 k words of length up to L. 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)

Worth mentioning; usually not worth writing first. The sorted key is shorter, obviously correct, and fast for L <= 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 dict (insertion-ordered since Python 3.7) to keep first-appearance order. “What if the strings are enormous?” — the count tuple avoids the log 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 s and p, return the start indices of all substrings of s that are anagrams of p, in ascending order.

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

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

An anagram of p has exactly 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.

Delete keys that reach zero

del window[left] when the count hits 0 is the detail that trips people up. If you leave {'a': 0} in the map, a plain-dict comparison against need fails even though the window really is an anagram.

Counter.__eq__ actually treats missing and zero-valued keys as equal, so with two Counters you could technically skip the del. But the deletion also keeps the map small and makes the code correct under either mental model — which is why it is worth writing rather than relying on a subtlety you would then have to defend.

("baa", "aa") giving [1] is the case that exercises this: at index 1 the window is "aa" and the count for b has just dropped to zero.

Comparing whole dicts is $O(|\Sigma|)$, so strictly the loop is $O(n \cdot |\Sigma|)$. For a tighter version, maintain a single matches counter tracking how many characters currently have the right count, and compare it against the number of distinct characters in p — 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 True on the first match. “Return the substrings instead of indices?” — slice at each hit. “Make each step truly $O(1)$?” — the matches-counter refinement above. “Unicode alphabet?” — space becomes $O(\min(n, |\Sigma|))$ and the dict-comparison cost grows, which is a stronger argument for the matches counter.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1657 is the one that tests whether you really understand keys

Two strings are “close” if you can transform one into the other by swapping characters and by relabelling one character class into another. So you need two things to match: the set of characters used (relabelling cannot introduce a new letter) and the sorted list of counts (swapping and relabelling permute which letter has which count, but not the counts themselves). set(a) == set(b) and sorted(Counter(a).values()) == sorted(Counter(b).values()). It is a two-line solution that is nearly impossible to guess without reasoning about what the operations preserve.

9 problems

5 easy4 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○242Valid Anagrameasy`Counter(s) == Counter(t)` after a length checkNeetCode 150Blind 75LeetCode Top Interview 150amazonmetabloomberg
• ○205Isomorphic StringseasyTwo maps, one per direction -- one is not enoughLeetCode Top Interview 150
• ○290Word Patterneasy205 over words instead of characters; check the lengths matchLeetCode Top Interview 150
• ○383Ransom NoteeasyMultiset containment -- `Counter(note) <= Counter(magazine)`LeetCode Top Interview 150
• ○387First Unique Character in a StringeasyCount in pass 1, then scan **in order** for the first count of 1
• ○49Group AnagramsmediumCanonical key into a `defaultdict(list)`NeetCode 150Blind 75LeetCode Top Interview 150amazonmetauberbloomberg
• ○438Find All Anagrams in a StringmediumFixed window + counter; delete zero-count keys
• ○451Sort Characters By Frequencymedium`most_common()`, or bucket by count for $O(n)$
• ○1657Determine if Two Strings Are ClosemediumSame character *set*, and the same sorted multiset of **counts**

Dry run

LC 242 Valid Anagram on "anagram" vs "nagaram", using one counter rather than two — increment for the first string, decrement for the second.

char	from	counter after
a	s	{a:1}
n	s	{a:1, n:1}
…	s	{a:3, n:1, g:1, r:1, m:1}
n	t	{a:3, n:0, g:1, r:1, m:1}
a	t	{a:2, n:0, …}
…	t	all zero

Final check: every value is 0, so they are anagrams. One counter and one pass beats two counters and a comparison, and it makes the length check unnecessary — different lengths leave a non-zero total.

Now the sliding case, LC 438 with p = "abc", s = "cbaebabacd":

i	window	window map vs need	match?
2	cba	{a:1,b:1,c:1} = {a:1,b:1,c:1}	yes, start 0
3	bae	e present, c absent	no
4	aeb	e present	no
5	eba	e present	no
6	bac	{a:1,b:1,c:1}	yes, start 4
7	aca	{a:2,c:1}, no b	no
8	cad	d present	no

Answer [0, 6]. Each step changes exactly two counts, which is what makes the per-step work constant.

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 Counter 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 matches 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 n, so no comparison sort is needed

Edge-case checklist

• Different lengths — an instant False for anagram checks; for LC 290 an explicit length check is required.
• Empty string — an anagram of itself; make sure Counter("") paths work.
• p longer than s (LC 438) — return [] before building a window you cannot fill.
• Every window matches — ("abab", "ab") gives [0,1,2], so overlaps count.
• Counts reaching zero — delete the key, or rely knowingly on Counter equality semantics.
• Repeated characters in the pattern — ("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.

Self-check

pch.quizTag Frequency and anagram counting — self-check

1. Why delete a key when its count reaches zero?

   A To save memory B Because a Counter with an extra zero-valued key is not equal to one without it, so the map comparison would silently fail C To keep the iteration order stable D It is unnecessary
   pch.quizShowAnswer

   B — Because a Counter with an extra zero-valued key is not equal to one without it, so the map comparison would silently fail — Python compares Counters by their full key sets. {a:1, b:0} != {a:1}. The logic looks correct and the answer comes back wrong, which makes this one of the harder bugs to spot in this pattern.

2. Why is comparing two frequency maps considered O(1) here?

   A Because dict comparison is a single machine instruction B Because the alphabet is bounded at 26, and 26 is a constant C Because the maps are always empty D It is not — the algorithm is O(26n)
   pch.quizShowAnswer

   B — Because the alphabet is bounded at 26, and 26 is a constant — The claim depends entirely on the bounded alphabet. If the input were arbitrary Unicode the comparison would be O(distinct characters) and the linear bound would not hold — worth stating as a precondition rather than assuming it.

3. For LC 242 Valid Anagram, what does the one-counter trick buy?

   A Nothing — two counters are equally good B One pass instead of two, and the length check becomes unnecessary since different lengths leave a non-zero total C It handles Unicode D It reduces space to O(1)
   pch.quizShowAnswer

   B — One pass instead of two, and the length check becomes unnecessary since different lengths leave a non-zero total — Increment for the first string, decrement for the second, then assert every count is zero. Both approaches are O(n); the single counter is just tidier and folds the length check in for free.

4. Group Anagrams (LC 49) needs a hash key per word. What is a good key?

   A The word itself B The sorted characters, or a 26-length count tuple — the count tuple is O(n) per word versus O(n log n) for sorting C The word length D The first and last characters
   pch.quizShowAnswer

   B — The sorted characters, or a 26-length count tuple — the count tuple is O(n) per word versus O(n log n) for sorting — Both keys work. Sorting is shorter to write; the count tuple is asymptotically better and worth mentioning even if you write the sort. Either way the insight is that anagrams share a canonical form.

Recall card

• Cue — anagrams, permutations, “same characters in any order”, or counting occurrences of a character multiset.
• Key idea — an anagram is a multiset. Reduce every word to a canonical form (sorted string, or a 26-length count tuple) and equality becomes a lookup.
• Sliding form — fixed window of len(p); each step increments one count and decrements another, then compares maps.
• Complexity — $O(n)$ time, $O(1)$ space given a bounded alphabet. State that precondition; it is what the constant rests on.
• Remember — delete zero-valued keys before comparing maps; for LC 242 use one counter (increment then decrement) rather than two.

Recap

• When order does not matter, discard it and keep the multiset — that reduction is the pattern.
• Counter 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)) 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 Counter.
• 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.