Frequency Counting
Scenario
You have two massive strings and need to know if they are anagrams of each other (contain the exact same letters in different orders).
Do you sort both strings which costs O(N log N) time, or is there a way to verify them in a single O(N) pass?
Why it exists
Problem: Comparing two collections of items to see if they share the same composition typically requires nested loops (O(N^2)) or sorting them first (O(N log N)). Both are too slow for massive datasets.
Naive approach: Sort both arrays or strings, then walk through them side-by-side to ensure they match exactly.
Better idea: Use a Hash Map to count the frequencies of every element in the first collection. Then, walk through the second collection and decrement those counts. If all counts reach zero, the collections are identical in composition. This takes O(N) time.
Mental model
Imagine comparing two bags of marbles. Instead of lining them all up by size (sorting), you just make a tally sheet: '3 red, 2 blue'. Then you pull marbles from the second bag and cross off the tallies. If you cross everything off perfectly, the bags match.
Frequency counting leverages a Hash Map to record occurrences of discrete elements. The keys are the elements themselves, and the values are integer counters. This transforms a sequence of data into a canonical signature (a histogram) that represents its exact makeup, ignoring order.
Repeated decision: Have we seen this element before? If yes, increment its count; if no, add it to the map with count 1.
Explanation
Frequency counting is the definitive pattern for problems involving permutations, anagrams, or occurrences.
To check if 'cinema' and 'iceman' are anagrams, we initialize an empty Hash Map. We iterate over 'cinema'. For 'c', we set its count to 1. For 'i', 1. By the end, our map is: `{'c': 1, 'i': 1, 'n': 1, 'e': 1, 'm': 1, 'a': 1}`.
Next, we iterate over the second string, 'iceman'. For every character, we look it up in the map and decrement its count. 'i' goes from 1 to 0. 'c' goes from 1 to 0.
If we ever try to decrement a character that isn't in the map, or if a count drops below zero, the strings are not anagrams. Finally, if the strings were of equal length and we never dipped below zero, we know with mathematical certainty that they are exact anagrams.
This exact same pattern solves problems like finding the majority element, finding the first non-repeating character, or checking if one string can be constructed from a magazine cutout (Ransom Note).
Key points
- O(N) Time: We iterate through the data exactly once (or twice). There is no nested iteration and no sorting.
- O(K) Space: The space complexity depends on the number of UNIQUE elements, not the total number of elements. For English letters, space is O(1) because there are only 26 possible keys.
- Canonical Signatures: A frequency map acts as a fingerprint. Any two anagrams will produce the exact same frequency map, allowing you to group them together easily.
Pattern: Frequency Map / Counting
Recognition cues:
- The problem asks about anagrams or permutations.
- You need to find elements that appear a specific number of times (e.g., 'majority element').
- The problem asks if you can construct string A from the letters of string B.
Failure signals
- You are using `.count()` inside a `for` loop (this is accidentally O(N^2) in most languages).
- You are calling a `.sort()` function to compare compositions.
Engineering examples
Text Analysis and NLP
Generating a Bag-of-Words model to feed text into a machine learning algorithm.
Frequency counting converts raw text into numerical vectors (word counts) that neural networks can process.
Rate Limiting
Tracking how many times an IP address has accessed a server in the last minute.
A Hash Map of `IP -> Request Count` provides instantaneous tracking to block abusers.
When not to use
- You need to maintain the original order of the elements: Hash Maps destroy ordering. If sequence matters, frequency counting is the wrong tool.
Common mistakes
- KeyError or NullPointer exceptions: When incrementing, you must check if the key already exists before adding 1 to it. Use `map.get(key, 0)` in Python or `map.getOrDefault(key, 0)` in Java.
- Not checking lengths first: If checking for valid anagrams, check if `len(s1) == len(s2)` immediately. If they differ, return false instantly and save O(N) work.
Glossary
- discrete elements
- Separate, individual items that can be counted individually.
- canonical signature
- A standardized, unique representation that identifies a collection of items.
- majority element
- An item that appears more than half the time in a given dataset.
Recall questions
- Why is frequency counting faster than sorting for checking anagrams?
- What is the space complexity of a frequency map of English letters?
- What two operations form the core of the frequency counting pattern?
Questions & answers
Given a string, find the first non-repeating character in it and return its index.
Pass 1: Build a frequency map of all characters. Pass 2: Iterate through the string again and check the map. The first character with a count of exactly 1 is the answer.
Approach: Two-pass frequency counting.
Given an array of strings, group the anagrams together.
For each string, build a frequency array (size 26). Convert that array into a tuple or string to use as a key in a Hash Map. Append the original string to the list of values for that key.
Approach: Frequency array as a canonical signature.
Interesting facts
- In Python, the `collections.Counter` module does this exact pattern automatically in highly optimized C code.
Continue learning
Previous: Hash Sets vs Maps
Related: Hash Tables
Related: Hash Sets vs Maps