Valid Anagram and Frequency Counting With a Hash Map

"Given two strings, return true if one is an anagram of the other." The textbook answer sorts both and compares. It works, and it quietly answers a harder question than the one asked. An anagram check only needs to know how many of each letter there are, and a hash map gets that in one pass.

The problem it solves

A whole family of questions turns out to be the same question in disguise:

• Valid anagram: do s and t contain exactly the same letters, the same number of times?
• First unique character: which is the first position whose character appears only once?
• Most common item: which value appears most often?
• Ransom note: can the letters of one string be taken from the letters of another?

Each has an O(n²) answer that re-scans the input for every element, s.count(ch) inside a loop, and an O(n log n) answer that sorts first. All of them have an O(n) answer built on a single frequency map.

The intuition

Walk the input once and keep one counter per distinct value: the first sighting creates the counter at 1, every later sighting adds one. When the walk ends, the counts are finished, and the answer is read off the map without touching the input again.

For anagrams there is a neat twist: use one map for both strings. Count up for each letter of s, count down for each letter of t. The strings are anagrams exactly when every counter ends at zero. If the lengths differ they cannot be anagrams, so that check comes first and costs nothing.

The idea generalises: a frequency map is a multiset, a set that remembers how many times each element appears. Two multisets are equal when every count agrees, which is the anagram definition word for word.

Watch it run

The animation walks the lesson's bird survey, robin, crow, robin, wren, crow, robin, one sighting at a time. Watch the first robin and the first crow: counts.get(item, 0) returns 0, so a new line starts at 1 instead of crashing. Every later sighting is one tick beside a line that already exists. When the route ends, robin × 3 is read straight off the map.

The code

The lesson's counter, then the anagram check with one map counting up and down:

def top_item(items):
    counts = {}
    for item in items:
        counts[item] = counts.get(item, 0) + 1
    return max(counts, key=counts.get)

def is_anagram(s, t):
    if len(s) != len(t):
        return False                     # different lengths: never anagrams
    counts = {}
    for a, b in zip(s, t):
        counts[a] = counts.get(a, 0) + 1
        counts[b] = counts.get(b, 0) - 1
    return all(c == 0 for c in counts.values())

print(top_item(["robin", "crow", "robin", "wren", "crow", "robin"]))   # robin
print(is_anagram("listen", "silent"), is_anagram("rat", "car"))       # True False

Python's collections.Counter is the same map with the bookkeeping done for you, and it makes the other family members one-liners:

from collections import Counter

def first_unique(s):
    counts = Counter(s)
    for i, ch in enumerate(s):           # second pass, in original order
        if counts[ch] == 1:
            return i
    return -1

def can_build(note, magazine):
    return not (Counter(note) - Counter(magazine))   # nothing left over

print(first_unique("swiss"), first_unique("aabb"))                    # 1 -1
print(can_build("aab", "baa"), can_build("aa", "ab"))                 # True False
print(Counter("mississippi").most_common(2))          # [('i', 4), ('s', 4)]

The counting check against the sorting definition and a brute force that tries every permutation, on 3,000 random pairs over a three-letter alphabet so that real anagrams are common:

import itertools, random

def brute_anagram(s, t):
    return any("".join(p) == t for p in itertools.permutations(s))

random.seed(3)
ok = True
anagrams = 0
for _ in range(3000):
    s = "".join(random.choice("abc") for _ in range(random.randint(0, 6)))
    t = "".join(random.choice("abc") for _ in range(random.randint(0, 6)))
    expected = sorted(s) == sorted(t)
    ok &= is_anagram(s, t) == expected == brute_anagram(s, t)
    anagrams += expected
print(ok, anagrams > 100)                # True True

The complexity

• Counting touches each character once, and each dictionary update is O(1) on average, so the whole check is O(n) time.
• Space is O(k), where k is the number of distinct characters. For a fixed alphabet such as 26 lowercase letters, that is a constant, and a list of 26 integers indexed by ord(ch) - ord("a") can replace the dictionary.
• Sorting both strings is O(n log n) time and O(n) extra space for the sorted copies. On short strings the difference rarely matters; the counting version wins on long inputs and is the one that generalises.
• Re-scanning with s.count(ch) for every character is O(n) per call, O(n²) in total.

Where it goes wrong

• Forgetting the default. counts[ch] += 1 on a plain dictionary raises KeyError on the first sighting. counts.get(ch, 0) + 1, defaultdict(int) or Counter all handle it.
• Skipping the length check in the one-map version. It is not just an optimisation: zip stops at the shorter string, so without the check, is_anagram("ab", "a") would compare only one pair and could report a false match.
• Case and spacing. "Dormitory" and "dirty room" are anagrams only after lower-casing and removing spaces. Decide the normalisation before counting, and say it out loud.
• Unicode. The same accented letter can be one code point or two, a base letter plus a combining mark. "é" == "é" is False in Python; normalising both strings with unicodedata.normalize("NFC", ...) first makes them compare equal.
• Ties. In the mississippi example, i and s both appear four times. max and most_common break ties by first insertion, which is a detail of Python, not of the problem. If the question has a tie rule, implement it.

How to say it in an interview

"Two strings are anagrams when they have the same letter counts, so I don't need to sort. After a length check I walk both strings once, adding one for each letter of s and subtracting one for each letter of t; they are anagrams if every count ends at zero. That's O(n) time and O(k) space for k distinct characters, which is constant for a fixed alphabet. Sorting would also work in O(n log n). I'd confirm whether case, spaces and Unicode need normalising first."

When the question moves from "are these two anagrams?" to "group all the anagrams", the count becomes a dictionary key, which is the step taken in group anagrams. Counting over a moving window instead of a whole string is the sliding window.