Frequency Counting and Grouping
Use Counter and defaultdict to count character frequencies, group anagrams by sorted key, and find top-k frequent elements.
Frequency Counting: The Core Pattern
Frequency counting is among the most versatile patterns in coding interviews. By tallying how often each element appears in a list or string, you can answer questions about duplicates, anagrams, most-common elements, and valid arrangements in O(n) time — much better than the O(n log n) sort-and-scan alternative.
Python's Counter and defaultdict(int) are the standard tools. Both create a mapping from element to count; Counter additionally supports arithmetic and most_common.
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]Valid Anagram (LeetCode 242)
LeetCode 242 'Valid Anagram': determine if two strings are anagrams of each other. Two strings are anagrams if they have the same character frequencies. Compare their Counter objects or sort both strings. Using Counter is O(n), sorting is O(n log n). The Counter approach is optimal and directly expresses the definition.
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # TrueAll lessons in this course
- Hash Function Internals and Collision Handling
- Two-Sum and Its Many Variants
- Frequency Counting and Grouping
- Longest Consecutive Sequence and LRU Cache