BeginnerArrays & Strings
Counting things with a hash map
Anagrams, majority element, most frequent: they're all “count each value”. A hash map from value to count does it in one pass.
The idea
A hash map (dict in Python) stores key → value pairs with O(1) lookups. Use the item as the key and how many times you've seen it as the value.
Two strings are anagrams exactly when every letter has the same count in both, so counting turns the problem into comparing two maps.
Worked example
Valid Anagram: “listen” vs “silent”
- Count “listen”: l:1 i:1 s:1 t:1 e:1 n:1
- Count “silent”: s:1 i:1 l:1 e:1 n:1 t:1
- Same keys with the same counts → anagram.
In code (Python)
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
# Without Counter:
def counts(s):
seen = {}
for ch in s:
seen[ch] = seen.get(ch, 0) + 1
return seenO(n) time, O(k) space for k distinct items.
How to spot it
- “anagram”, “frequency”, “most common”, “appears more than n/2 times”.
Common mistakes
- Forgetting the length check shortcut: different lengths can't be anagrams.
- Sorting both strings works but is O(n log n); counting is O(n).
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →