1Understand
The idea
Count occurrences with a frequency map, or map each item to a canonical key (sorted letters, a tuple of counts) so that items that should be grouped together share the same key. Two collections are "the same up to order" exactly when their counts match.
Intuition
Counting problems ask how often something appears; grouping problems ask which items share a property. Both start from a frequency map or a canonical key that makes equivalents look identical (sorted letters, a 26-tuple of counts, a frozenset).
Two collections are the same up to order exactly when their counts match. Counter makes that comparison one line; a hand-built dict is the same idea.
Choose the cheapest key that distinguishes groups: sorting a string is O(k log k); a count tuple over a fixed alphabet is O(k).
What you will be able to do
- Build frequency maps
- Design a canonical key (sorted string, count tuple)
When to use it
- Anagrams or permutations of each other
- Most / least frequent
- Group items that share a property
2See it
Walkthrough
Group anagrams by key
words = ["eat", "tea", "tan"], canonical key = sorted letters.
1 / 4
groups
- ∅ empty
Empty groups. For "eat", key = "aet".
Live template
Line 3 active
Complexity: time O(n·k), space O(n)
Building groups is O(n · cost(key)). Space is O(n) to hold the items. Fixed-alphabet count keys beat sorting when k is large. If you only need the most frequent key, a heap or bucket sort on frequencies can avoid a full sort of n items.
Read the walkthrough as text
Group anagrams. Words ["eat","tea","tan","ate","nat","bat"].
- For each word, build key =
tuple(sorted(word))(or a 26-length count tuple). - Append the word to
groups[key]. - After one pass, the map values are the groups:
{('a','e','t'): ["eat","tea","ate"]...}.
Valid anagram of two strings is the special case with one group of size two: compare two Counters (or one count array incremented then decremented to all zeros).
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Frequency comparison (valid anagram)
Example. Are two strings permutations of each other?
How. Count each letter with Counter (or a size-26 array); equal multisets ⇔ anagram.
Grouping by canonical key
Example. Group strings that are anagrams.
How. Key = sorted(s) or tuple of counts; defaultdict(list) buckets items with the same key.
Majority or most frequent element
Example. Element that appears more than n/2 times, or top frequent words.
How. Count once, then scan counts or use a heap / bucket by frequency for top-k.
Bucket sort by frequency
Example. Sort array by how often each distinct value appears.
How. freq[value] → index into buckets; walk buckets from high frequency to low.
Counting pairs with a property
Example. Number of equal-value pairs, or pairs with a given difference.
How. As you scan, add count[need] to the answer, then increment count[current].
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Unhashable key
Why it happens. A list or dict is used as a dict key when grouping.
How it fails. groups[[1,2]] = … raises TypeError: unhashable type: list.
Fix. Convert to tuple, frozenset, or string key before using as dict key.
Count comparison
Why it happens. Comparing two Counter objects or maps after partial updates.
How it fails. Anagram check returns true when one map still has a letter the other never had (missing key treated as zero incorrectly).
Fix. Compare counts for every letter in the union of keys, or use Counter subtraction and test emptiness.
Expensive key
Why it happens. Sorting every string as the key is simpler mentally but costly per item.
How it fails. n strings length k each: sorting all n keys costs O(n·k log k) where a count tuple is O(k).
Fix. Use tuple(counts) or Counter; sort only when the key must be canonical and k is tiny.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.