Frequency Map Pattern — LeetCode #242: Valid Anagram

Prerequisites: Loop Invariants (first post — what an invariant is) | Running Sum (#1480) | Contains Duplicate (#217) — the "have I seen this?" foundation)

Contains Duplicate asks "does X exist?" — this post asks "how many of X exist?" Same data structure, deeper question. Each post builds one layer on top of the last.

The Problem (15 seconds)

Given two strings s and t, return true if t is an anagram of s.

An anagram uses the exact same characters, the exact same number of times, in any order.

Input:  s = "anagram", t = "nagaram"
Output: true

Input:  s = "rat", t = "car"
Output: false

LeetCode #242 — Valid Anagram

My First Instinct

"If they're anagrams, they have the same letters in the same quantities — just rearranged."

The simplest way to check: sort both strings and compare.

// Brute force — sort and compare
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  return [...s].sort().join('') === [...t].sort().join('');
}

This works. O(n log n) for the sorts. But it's doing more work than necessary — sorting arranges every character into position, when all we care about is whether the counts match.

Sorting answers "are these the same sequence?" We're asking a weaker question: "do these have the same ingredients?"

The Reframe

Don't compare sequences. Compare inventories.

An anagram isn't about order — it's about quantity. "anagram" and "nagaram" have the same inventory: {a:3, n:1, g:1, r:1, m:1}.

So the real question is: do both strings have identical character counts?

You could build two frequency maps and compare them. But there's a cleaner trick: use one map and track the difference.

• Walk through s: increment each character's count
• Walk through t: decrement each character's count
• If every count is 0 at the end → perfect match → anagram

This is a universal principle: when comparing two things, don't build two copies — track the gap between them.

The Invariant

After processing s[0..i-1] and t[0..i-1], counts[char] = (occurrences in s so far) minus (occurrences in t so far).

This is a difference invariant — the map doesn't store absolute counts, it stores the imbalance between the two strings.

Let's verify with the 3-step check:

1. Before the loop: counts = {} → difference is 0 for all characters → ✓
2. After each step: we increment for s[i], decrement for t[i] → the difference for those characters is updated → ✓
3. When done: if all counts are 0 → every character that s added was consumed by t → anagram → ✓

Solution

TypeScript:

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const counts = new Map<string, number>();

  for (let i = 0; i < s.length; i++) {
    counts.set(s[i]!, (counts.get(s[i]!) ?? 0) + 1);
    counts.set(t[i]!, (counts.get(t[i]!) ?? 0) - 1);
  }

  for (const count of counts.values()) {
    if (count !== 0) return false;
  }

  return true;
}

Python:

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    counts: dict[str, int] = {}

    for sc, tc in zip(s, t):
        counts[sc] = counts.get(sc, 0) + 1
        counts[tc] = counts.get(tc, 0) - 1

    return all(v == 0 for v in counts.values())

Complexity: O(n) time, O(1) space (at most 26 lowercase letters — the map is bounded).

Note the space: even though we use a hash map, the keys are limited to 26 characters. This is O(1) space, not O(n). Recognizing bounded key spaces matters — interviewers will ask.

Dry Run

s = "anagram", t = "nagaram"

i=0: s='a' t='n' → counts = {a:1, n:-1}
i=1: s='n' t='a' → counts = {a:0, n:0}
i=2: s='a' t='g' → counts = {a:1, n:0, g:-1}
i=3: s='g' t='a' → counts = {a:0, n:0, g:0}
i=4: s='r' t='r' → counts = {a:0, n:0, g:0, r:0}
i=5: s='a' t='a' → counts = {a:0, n:0, g:0, r:0}
i=6: s='m' t='m' → counts = {a:0, n:0, g:0, r:0, m:0}

All zeros → return true ✓

Watch how the counts fluctuate — a goes to 1, back to 0, up to 1, back to 0. The invariant doesn't require counts to be 0 during the loop — only at the end. That's the difference between an invariant (what's always true) and the final condition (what the invariant guarantees when the loop exits).

Now a failing case:

s = "rat", t = "car"

i=0: s='r' t='c' → counts = {r:1, c:-1}
i=1: s='a' t='a' → counts = {r:1, c:-1, a:0}
i=2: s='t' t='r' → counts = {r:0, c:-1, a:0, t:1}

c=-1, t=1 → NOT all zeros → return false ✓

c:-1 means t has a c that s doesn't. t:1 means s has a t that t doesn't. The map tells you exactly which characters don't match and by how much.

The Variant: Two Separate Loops

Some solutions process s fully, then t fully — two separate passes:

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const counts = new Map<string, number>();

  for (const char of s) {
    counts.set(char, (counts.get(char) ?? 0) + 1);
  }

  for (const char of t) {
    const count = (counts.get(char) ?? 0) - 1;
    if (count < 0) return false;  // t has a char that s doesn't (or too many)
    counts.set(char, count);
  }

  return true;
}

This version can exit early in the second loop — the moment any count goes negative, t has a character s can't provide. The single-loop version is cleaner; this version is faster on mismatches. Both are O(n). Choose based on what you're optimizing for: clarity or early exit.

Three Universal Truths

These principles show up far beyond this problem:

1. "Track the difference, not two copies"

Instead of building two frequency maps and comparing them key by key, we used one map tracking the imbalance. This principle appears everywhere:

• Balanced parentheses: don't count opens and closes separately — track the net depth
• Subarray Sum Equals K: don't store all sums — track the prefix sum difference
• Two Sum: don't compare all pairs — compute the complement (target minus current)

The pattern: when you need to check if two things match, subtract one from the other and check if the result is zero.

2. "Bounded keys = O(1) space"

The hash map has at most 26 entries (lowercase English letters). Even though we use a hash map, the space doesn't grow with input size. Recognizing bounded key spaces is a real interview skill — it turns an O(n) space argument into O(1).

Other bounded-key situations:

• ASCII characters (128 keys)
• Digits (10 keys)
• Boolean flags (2 keys)
• Lowercase letters (26 keys)

3. "Existence → Set. Counting → Map. The question determines the data structure."

Contains Duplicate (#217) asked "does X exist?" → Set.
This problem asks "how many of X exist?" → Map.

The only difference is what you store alongside the key:

• Set: just the key (existence)
• Map with count: key → how many (frequency)
• Map with index: key → where (position, like Two Sum)
• Map with list: key → which ones (grouping, like Group Anagrams)

Each upgrade adds information. The question you're asking determines which level you need.

Where This Pattern Shows Up Again

What I Learned

1. "Track the difference, not two copies." This is the single biggest insight from this problem. Whenever you're comparing two collections, one map tracking the imbalance is cleaner, faster, and more elegant than two maps plus a comparison step.

2. The frequency map is a hash map upgrade. Contains Duplicate taught "is X in the set?" (boolean). This problem teaches "how many X are there?" (count). Two Sum will teach "where is X?" (index). Each problem adds one layer to the same data structure.

3. The invariant tells you what's in the map at every step. counts[char] = difference in frequencies so far. At the end, the invariant + exit condition (all zeros) = the answer (anagram). Same 3-step verification as every other problem.

4. O(1) space with bounded keys. Don't say "O(n) space" in an interview when the key space is fixed. 26 letters → O(1). This distinction matters.

What's a problem where you compared two things the hard way — two copies, full comparison — and only later realized you could've tracked the gap instead?

This post is part of the LeetCode Patterns series. You've now practiced three building blocks: Running Sum (#1480) (accumulator invariant), Contains Duplicate (#217) (hash set lookup), and Valid Anagram (frequency map). Next: bring all three together in Two Sum (#1) — where the hash map stores indices, the lookup finds complements, and the invariant ties it all together.