Frequency Counting Pattern

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 2 Time to complete: ~20 minutes

The Pattern
Counting with a Plain Dict
Counting with collections.Counter
Worked Example: First Non-Repeating Character
Worked Example: Anagram Check via Counting
Summary & Next Steps

1. The Pattern

The frequency counting pattern is: build a hash map from each distinct item to how many times it appears, then answer the actual question using that map. It's one pass to build the map (O(n)), then typically one more pass or lookup to answer the question — the entire pattern usually runs in O(n) time and O(n) space (or O(k) space, where k is the number of distinct items).

2. Counting with a Plain Dict

def count_chars(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1      # Chapter 1's safe-increment idiom
    return counts
 
print(count_chars("banana"))
# {'b': 1, 'a': 3, 'n': 2}

3. Counting with `collections.Counter`

Counter is a dict subclass purpose-built for exactly this pattern — it's the idiomatic tool for frequency counting in Python:

from collections import Counter
 
counts = Counter("banana")
print(counts)                    # Counter({'a': 3, 'n': 2, 'b': 1})
print(counts.most_common(2))     # [('a', 3), ('n', 2)] — top 2 most frequent
print(counts["z"])                # 0 — missing keys default to 0, no KeyError
 
words = Counter(["apple", "banana", "apple", "cherry", "apple"])
print(words)                       # Counter({'apple': 3, 'banana': 1, 'cherry': 1})

Counter also supports arithmetic directly — counter_a + counter_b merges counts, counter_a - counter_b subtracts them (dropping non-positive results). This comes up often when comparing two frequency profiles at once.

4. Worked Example: First Non-Repeating Character

Problem: Given a string, return the index of the first character that appears exactly once.

def first_unique_char(s):
    counts = Counter(s)                  # O(n) — build frequency map
 
    for i, char in enumerate(s):          # O(n) — scan in original order
        if counts[char] == 1:
            return i
    return -1
 
print(first_unique_char("leetcode"))     # 0 → 'l' is the first char with count 1
print(first_unique_char("aabb"))          # -1 → no unique character

Complexity: O(n) time (two linear passes), O(k) space where k is the number of distinct characters — a strict improvement over a naive approach that re-scans the string for every character (O(n²)).

5. Worked Example: Anagram Check via Counting

Module 2 Chapter 6 solved this by sorting both strings and comparing (O(n log n)). The frequency-counting version is faster:

def is_anagram(s1, s2):
    if len(s1) != len(s2):
        return False
    return Counter(s1) == Counter(s2)     # O(n) build + O(k) comparison
 
print(is_anagram("listen", "silent"))    # True
print(is_anagram("hello", "world"))       # False

Complexity: O(n) — building both counters is linear, and comparing two Counter objects (dicts under the hood) is proportional to the number of distinct characters, not n log n. This is a direct, concrete example of hashing turning an O(n log n) solution into an O(n) one.

6. Summary & Next Steps

Key Takeaways

The frequency counting pattern — build a count map, then answer the question from it — runs in O(n) time for most problems that ask "how many," "which is most/least common," or "do these have the same composition."
collections.Counter is the idiomatic Python tool for this pattern, with .most_common() and direct arithmetic (+, -) as bonuses.
Comparing frequency maps (Counter(s1) == Counter(s2)) is often a faster anagram check than sorting both strings.

Concept Check

Why does counts.get(char, 0) + 1 avoid a KeyError on the first occurrence of a character?
Why is the Counter-based anagram check O(n) while sorting-based anagram check is O(n log n)?
What does Counter.most_common(k) return?

Next Chapter

→ Chapter 4: Common Hashing Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index