Frequency Counting

How It Works

Frequency counting builds a tally of how many times each distinct value appears — using a hash map for arbitrary values, or a fixed-size array (length 26 for lowercase letters, 128/256 for ASCII) when the alphabet is small and known in advance. Once the tally exists, most questions about the input's composition become O(1) lookups instead of repeated scans or comparisons.

Two counts are "the same multiset" (e.g. anagrams) exactly when every key maps to the same value in both frequency maps. Finding the most/least frequent element is a matter of scanning the tally once instead of sorting the original input. "First unique character" becomes: build the tally in one pass, then scan the original string again and return the first character whose count is 1.

The fixed-size-array variant is worth calling out explicitly: when you know input is restricted to lowercase English letters, an array of 26 counters is faster and simpler than a hash map, and makes the O(1) space claim precise rather than "O(n) but n is capped at 26."

When To Use It

Reach for frequency counting when:

• The problem is explicitly about anagrams, permutations of characters, or "rearranged" strings.
• You need to detect duplicates, or count how many times something repeats.
• You need the most frequent or least frequent element(s) — a frequency map plus a sort/heap on the counts beats repeatedly scanning the original array.
• The problem asks for the first (or only) element/character that is unique.
• The brute force would involve comparing every pair of elements, or sorting purely to group equal values together.

Time & Space Complexity

• Time: O(n) to build the frequency tally, plus O(n) or O(n log n) to act on it (e.g. sorting counts for "top k frequent").
• Space: O(n) for a hash map in the general case; O(1) (technically O(1) bounded by alphabet size, e.g. 26) when the input is restricted to a small fixed alphabet.

Pattern Template

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

  const counts = {};
  for (const ch of s) {
    counts[ch] = (counts[ch] || 0) + 1;
  }

  for (const ch of t) {
    if (!counts[ch]) return false; // missing or already exhausted
    counts[ch]--;
  }

  return true;
}

Alternative Approaches

• Sorting: sort both strings/arrays and compare directly — O(n log n) time, O(1) extra space (or O(n) depending on sort implementation). Simpler to reason about than a hash map, but strictly slower.
• Bit manipulation: for problems restricted to distinct characters with no repeats allowed (e.g. "contains all unique characters"), a bitmask can replace a frequency map entirely and fit the whole state in a single integer.
• Two-pass array scan without a map: only works for narrow special cases (e.g. finding a single non-duplicate when everything else appears exactly twice, solvable with XOR) — not a general substitute for frequency counting.

Common Mistakes

• Using an object/hash map when a fixed-size array would be both faster and clearer for small, known alphabets.
• Forgetting that two anagrams must have equal length — skipping that early check wastes work building tallies that were doomed to mismatch anyway.
• For "top k frequent," sorting the original array instead of sorting the (value, count) pairs derived from the frequency map — these are different sorts with different complexity implications.
• Not resetting or scoping the frequency map correctly when checking multiple independent windows or strings in the same pass (state leaking between iterations).

Pattern Summary

Frequency counting replaces repeated pairwise comparisons or full re-scans with a single tally built in one pass. It's the default tool for anagram checks, duplicate detection, and "most/least/first unique" questions — swap in a fixed-size array instead of a hash map whenever the alphabet is small and known.