Frequency Counting

1. The signal

• “How many times does each … appear?”
• “Are these two anagrams / permutations of each other?”
• “Find the k most frequent …”
• “Group these together.”
• “Does any value appear more than once / more than n/2 times?”
• Any Sudoku-style “no repeats in this row, column, or box”.

The tell is that the answer depends on how many, not where. That means you can throw away position information — and once you do, the problem usually collapses to one pass.

2. The three shapes

Count into a map:

unordered_map<char,int> freq;
for (char c : s) freq[c]++;

const freq = new Map();
for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1);

Count into an array (when keys are dense small integers — prefer this):

vector<int> freq(26, 0);
for (char c : s) freq[c - 'a']++;

const freq = new Array(26).fill(0);
for (const c of s) freq[c.charCodeAt(0) - 97]++;

Group by a canonical key:

unordered_map<string, vector<string>> groups;
for (auto& s : strs) {
    string key = s;
    sort(key.begin(), key.end());     // every anagram → the same key
    groups[key].push_back(s);
}

const groups = new Map();
for (const s of strs) {
  const key = [...s].sort().join('');
  if (!groups.has(key)) groups.set(key, []);
  groups.get(key).push(s);
}

3. Why it works

Counting converts a comparison problem into an equality problem. “Is t an anagram of s?” is hard to answer by comparing strings directly, but trivial once both are count vectors: just compare the vectors. You’ve traded O(n) space for the ability to answer in O(n) time instead of O(n log n) or worse.

Grouping works for the same reason: a canonical key makes “are these in the same group?” an equality test, and equality is what hash maps are built for.

4. Complexity

Counting is O(n) time and O(k) space, where k is the alphabet size — O(1) when the alphabet is fixed, which is worth saying out loud for a 26-letter count. Grouping n strings of length m is O(n·m log m) with a sorted key, or O(n·m) with a count signature.

5. Variants

• Bucket by count — an array where index i holds the values seen exactly i times. Gives you top-k in O(n), beating the O(n log k) heap answer. This is the intended solution to Top K Frequent Elements.
• Count signature as a key — instead of sorting each string, use its 26-length count as the map key. O(m) per string instead of O(m log m).
• Running count with a window — the same idea, but adding and removing as a window slides. That’s all of week 2.
• Count of counts — for “can these be rearranged so that…” style questions.

6. Traps

1. Comparing lengths first. Two strings of different lengths can’t be anagrams. One line, saves the whole loop, and interviewers notice when you skip it.
2. Assuming lowercase ASCII. A 26-slot array plus an uppercase character is out-of-bounds in C++ and a silent wrong answer in JavaScript. Read the constraints.
3. Sorting to find top-k. O(n log n) when bucketing gives O(n).
4. Forgetting that a hash map has no order. If the output must be sorted or in first-seen order, you need to track that separately.

7. Problems, easiest first

1. Contains Duplicate — the set, in isolation
2. Valid Anagram — count, don’t sort
3. Group Anagrams — the canonical key
4. Top K Frequent Elements — bucket by count
5. Valid Sudoku — nine sets at once, and the box-index formula