Lesson 10 — Frequency Counting

~25 minutes · strings · Python

Tonight you meet Valid Anagram: two strings contain the same letters, but maybe in a different order. Interviewers like this shape because the obvious solution feels simple, yet the reusable idea underneath powers a whole family of grouping problems.

The invariant

Two strings are anagrams iff their letter-count histograms match; the histogram is also a perfect grouping key.

A histogram just means: count how many times each letter appears. For the LeetCode version, the inputs are lowercase English letters, so the histogram can be a 26-slot list: slot 0 for a, slot 1 for b, and so on.

What Python gives you

Python gives you the pieces you need:

• ord turns a one-character string into its code point, so ord(ch) - ord("a") maps lowercase letters to slots 0..25.
• Hashable objects can be dictionary keys. A tuple of counts can be a key; a mutable list cannot.

That second fact matters for Group Anagrams. Once a histogram becomes a tuple, every anagram lands under the same dictionary key.

A tuple of counts ignores letter order, so matching anagrams share one dictionary bucket.

Valid Anagram: the slow way first

The problem: return whether s and t are anagrams. A direct approach is to sort both strings and compare the sorted results:

def is_anagram(s, t):
    return sorted(s) == sorted(t)

This works, but sorting does extra work. It fully orders the letters, while an anagram only cares about counts. Sorting costs O(n log n); a histogram scan costs O(n) because each character is touched once (Python wiki: time complexity).

Valid Anagram: the histogram way

Use one 26-slot count list. Add letters from s; subtract letters from t. If the two histograms match, every slot returns to zero.

Matching letters cancel in the same array slots; a leftover nonzero count means not an anagram.

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - ord("a")] += 1  # one more a from s
        count[ord(b) - ord("a")] -= 1  # one b canceled by t
    return all(x == 0 for x in count)

The length check matters. Without it, zip stops at the shorter string, and extra trailing letters would never be counted.

Transfer: same histogram, new job

Group Anagrams: given a list of words, group words that are anagrams of each other.

Before opening the reveal: predict the key. If anagrams have matching histograms, what should all anagrams share inside a dictionary?

def group_anagrams(strs):
    groups = {}
    for word in strs:
        count = [0] * 26
        for ch in word:
            count[ord(ch) - ord("a")] += 1
        key = tuple(count)             # immutable grouping key
        groups.setdefault(key, []).append(word)
    return list(groups.values())

What the trade buys you

For grouping m words of average length k, the same trade is sorting keys in O(m · k log k) versus histogram keys in O(m · k).

Practice — answer before you scroll past

count = [0] * 26
for ch in s:
    count[ord(ch) - ord("a")] += 1
for ch in t:
    count[ord(ch) - ord("a")] += 1
return all(x == 0 for x in count)

Your move (tonight)

Solve these on LeetCode, in order, logging each in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Valid Anagram — predict the histogram, attempt the 26-slot version, then compare.
2. Group Anagrams — predict the grouping key before writing code.

For the encode step, write the invariant from this page in your own words. Revision days should test that sentence, not your memory of the exact code.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.