Frequency Counting with Python Dictionaries and Sets

From repeated comparisons to remembered information

Imagine validating a manifest of audio recording IDs and checking whether the same recording accidentally appears twice:

recording_ids = ["spk01_0001", "spk07_0003", "spk01_0001"]

A direct but poor approach is: for every ID, scan the rest of the list to see whether it occurs again.

def has_duplicate_brute_force(ids):
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False

The inner comparison happens for many pairs of IDs, so this is $O(n^2)$ time in the worst case.

But to decide whether the current ID is a duplicate, we do not need to compare it against every earlier item individually. We only need one piece of information:

Has this ID appeared already?

That is a membership question, and Python’s set is designed for expected constant-time membership testing.

The essential change is a time–space trade-off:

The extra memory is often worthwhile. For large dataset manifests, labels, speaker IDs, or token sequences, eliminating quadratic comparisons can be decisive.

Sets: the minimal form of frequency tracking

A set stores unique values. Its invariant in a duplicate-detection algorithm is:

Before processing item, seen contains exactly the distinct items that occurred earlier in the input.

def has_duplicate(items):
    seen = set()

    for item in items:
        if item in seen:
            return True
        seen.add(item)

    return False

Trace this on:

items = [8, 3, 5, 3]

The order of the two operations matters. If you added an item before checking membership, every item would appear to be a duplicate of itself.

Complexity

Let $n$ be the number of items and $u$ be the number of unique items.

• Time: expected $O(n)$. Each loop iteration performs a set membership test and possibly an insertion, both expected $O(1)$.
• Auxiliary space: $O(u)$, which is $O(n)$ in the worst case when all items are distinct.
• Best-case time: $O(1)$ if the second item is already a duplicate.

The word expected matters. Python dictionaries and sets are hash tables. Under normal hashing assumptions, lookup and insertion are expected $O(1)$; pathological collision behavior can be worse. In interview analysis, expected $O(1)$ per operation is the conventional and appropriate assumption unless the question explicitly asks about adversarial hashing.

This concise alternative is valid:

def has_duplicate_compact(items):
    return len(set(items)) != len(items)

It is still expected $O(n)$ time and $O(n)$ space, but it always processes the whole collection. The explicit loop is often better in an interview because it exposes the invariant and supports early exit.

One Python detail worth locking in now:

empty_dict = {}
empty_set = set()

{} creates an empty dictionary, not an empty set.

When a set is insufficient: multiplicity matters

A set answers only whether an item exists. It deliberately discards frequency.

For example:

set("aab") == set("abb")

evaluates to True, because both sets are:

{"a", "b"}

Yet "aab" and "abb" do not contain the same character frequencies:

If the prompt asks about:

• anagrams or permutations,
• exact composition,
• number of occurrences,
• most frequent elements,
• unique elements appearing exactly once,

you need a dictionary rather than just a set.

A frequency dictionary maps each item to its current count:

def build_frequency_map(items):
    counts = {}

    for item in items:
        counts[item] = counts.get(item, 0) + 1

    return counts

For:

build_frequency_map("banana")

the result is:

{"b": 1, "a": 3, "n": 2}

The important expression is:

counts.get(item, 0)

It means:

• return counts[item] if item is already a key;
• otherwise return 0.

Without .get, this would fail on the first occurrence of every new item:

counts[item] = counts[item] + 1  # KeyError if item is absent

The general frequency-map template is worth memorizing:

counts = {}

for item in items:
    counts[item] = counts.get(item, 0) + 1

It works for characters, integers, words, speaker IDs, labels, or tuples of immutable metadata fields. Dictionary keys and set elements must be hashable: strings, integers, and tuples of hashable values work; a mutable list does not.

Solving a full frequency-counting problem: valid anagram

Two strings are anagrams when they contain exactly the same characters with exactly the same frequencies, regardless of order.

Examples:

"anagram", "nagaram"  # True
"rat", "car"          # False
"aab", "abb"          # False

A straightforward dictionary solution builds one count map per string:

def is_anagram_two_maps(s, t):
    if len(s) != len(t):
        return False

    count_s = {}
    count_t = {}

    for ch in s:
        count_s[ch] = count_s.get(ch, 0) + 1

    for ch in t:
        count_t[ch] = count_t.get(ch, 0) + 1

    return count_s == count_t

Dictionary equality is exactly what we need here: two dictionaries are equal if they have the same keys and the same associated values.

The initial length check is not required for correctness, but it is useful:

if len(s) != len(t):
    return False

Strings of different lengths cannot be anagrams, so there is no reason to build maps for them.

Complexity of the two-map solution

Let $n=\text{len}(s)$ and $m=\text{len}(t)$.

• Building count_s takes expected $O(n)$.
• Building count_t takes expected $O(m)$.
• Comparing the maps takes time proportional to their distinct keys, at most $O(n+m)$.

Therefore, total time is:

The extra space is proportional to the number of distinct characters stored. In the general case this is:

where $u_s$ and $u_t$ are the numbers of unique characters. In the worst case, this is $O(n+m)$.

One dictionary: store the difference in counts

The two-map solution is the clearest first implementation. Once it is solid, you can reduce storage by using one dictionary as a difference map.

1. Count every character in s.
2. Process t, decrementing its characters.
3. If a count becomes negative, t requires more of a character than s provides.

def is_anagram(s, t):
    if len(s) != len(t):
        return False

    counts = {}

    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1

    for ch in t:
        counts[ch] = counts.get(ch, 0) - 1

        if counts[ch] < 0:
            return False

    return True

Trace the non-anagram case:

s = "aab"
t = "abb"

After counting s:

counts = {"a": 2, "b": 1}

Then process t:

Why can the function return True without explicitly checking that all counts are zero? The strings have equal length. We add exactly $n$ total counts while processing s, then subtract exactly $n$ counts while processing t. If no count ever became negative, all final counts are nonnegative and sum to zero—so every count must be zero.

A subtle implementation trap: do not increment from s and decrement from t in the same paired loop when using one difference map. Consider:

s = "ab"
t = "ba"

If you process a from s and immediately decrement b from t, the count for b temporarily becomes negative—even though b appears later in s. Build the full positive inventory from s first, then decrement with t.

Counter: concise, but know the underlying pattern

Python provides collections.Counter, which builds a frequency dictionary for you:

from collections import Counter

def is_anagram_counter(s, t):
    return Counter(s) == Counter(t)

This is idiomatic production Python. Still, in an interview, start by explaining the count-map idea and implement it manually unless the interviewer invites library shortcuts. The manual version demonstrates that you understand the state, invariants, and complexity rather than merely recognizing a utility.

Choosing the right structure quickly

Use this decision rule while reading a prompt:

A fixed-size array of length 26 can be slightly faster for a problem that explicitly guarantees lowercase English letters. Its auxiliary space is $O(1)$, because 26 does not grow with input size. But a dictionary is more general: it works when the domain includes arbitrary Unicode characters, words, token IDs, or metadata categories. Default to a dictionary unless the input contract makes the fixed domain meaningful.

Key takeaways

Frequency counting changes the problem from “compare this item with many others” to “update or query compact state.”

• Use a set when presence is sufficient. The check-then-add pattern detects duplicates in expected $O(n)$ time.
• Use a dictionary when multiplicity matters. The core update is:

counts[item] = counts.get(item, 0) + 1

• For anagrams, compare frequency maps or build one map from the first string and decrement it using the second.
• Hash-table operations are expected $O(1)$, so one-pass set and dictionary solutions are generally expected $O(n)$ time, with $O(u)$ extra space for $u$ distinct values.
• State the invariant of your data structure during interviews; it makes both correctness and complexity easier to explain.

Next, you will use the two-pointer technique on sorted arrays. Unlike frequency counting, where order is often irrelevant, two pointers exploit sorted order to eliminate impossible candidates without checking every pair.