Hashing Fundamentals
What is this?
This is where you learn the three everyday jobs a hash structure does. Use a set to check "have I seen this before?", a Counter to answer "how many of each do I have?", and a canonical key to lump together things that are secretly the same (like words that are anagrams). Each one replaces a slow, item-by-item comparison with one quick pass.
💡 Fun fact: The "group things that are secretly the same" trick has a famous twist — to detect anagrams you can multiply a prime number per letter, since every word maps to a unique product. This is essentially the Fundamental Theorem of Arithmetic, a 2000-year-old idea from Euclid, repurposed as a hash key.
🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Before the clever "what to store" tricks, master the three everyday uses of a hash structure: a set to test distinctness, a Counter to tally "how many of each", and a canonical key to group items that are secretly the same. Each turns an O(n²) scan into one O(n) pass.
The three reflexes
| Reflex | Trigger phrase | Tool |
|---|---|---|
| Set | "distinct / unique / seen" | set() |
| Frequency | "how many of each / most common / counts" | collections.Counter |
| Canonical key | "group the ones that are the same under …" | dict keyed by a normalized form |
The five problems
- Distribute Candies — a set gives the distinct-type count; answer
min(distinct, n//2). - Minimum Steps to Make Anagram — subtract two frequency tables; the deficit is the answer.
- Bulls and Cows — bulls by position, then count the leftover digits and sum
minof the two tallies for cows. - Longest Harmonious Subsequence — count values; for each
v, combinecount[v] + count[v+1]. - Group Shifted Strings — build a canonical key (mod-26 difference tuple) and group by it.
The pattern
Counting collapses "compare every element to every other" into "tally once, then read the tallies." A set answers membership in O(1). And when items are equivalent under some transformation (a shift, a sort, a rotation), compute a canonical form and let the map group them — the same trick behind Group Anagrams.
📓 Draw it yourself
- Two tally tables. For Bulls and Cows or the anagram problem, draw both frequency tables and read the answer off the per-letter differences.
- Canonical key. For Group Shifted Strings, write a few strings and their difference-tuple keys; watch equivalent ones land in the same bucket.
Snap photos and embed them with the /host-diagrams skill.
Key takeaways
- Three reflexes: set (distinct), Counter (how many), canonical key (group equivalents).
- Counting beats nested comparison — tally once in O(n), then answer questions off the tallies.
- A canonical key turns "are these equivalent?" into "do they hash the same?"
- Why it matters: these are the bread-and-butter hash moves every harder problem composes from.
Order: Distribute Candies → Min Steps to Make Anagram → Bulls and Cows → Longest Harmonious Subsequence → Group Shifted Strings.
Distribute Candies
Core idea: You can't eat more than half the pile, and you can't eat more distinct flavors than actually exist — so the answer is simply
min(distinct flavors, half the pile), and a set computes "distinct flavors" in one pass.
Problem, rephrased
You're at a tasting event with a tray of chocolates. The tray always holds an even number of chocolates, and each chocolate has a flavor printed on it (some flavors repeat). A rule of the event: you may eat exactly half the chocolates on the tray — no more, no fewer. You're a flavor collector, so you don't care how many chocolates you eat; you care how many different flavors you get to taste.
Question: if you pick your half optimally, what is the maximum number of distinct flavors you can taste?
Formally: given an even-length array candies where each value is a flavor id, you may select exactly len(candies) // 2 elements. Return the maximum number of distinct values among your selection.
Input candies |
n | n/2 | distinct flavors | Output | Why |
|---|---|---|---|---|---|
[1,1,2,2,3,3] |
6 | 3 | 3 | 3 | 3 flavors exist, you may eat 3 → take all 3 |
[1,1,2,3] |
4 | 2 | 3 | 2 | 3 flavors exist but you may eat only 2 |
[6,6,6,6] |
4 | 2 | 1 | 1 | only 1 flavor exists, so at most 1 |
[1,2,3,4,5,6] |
6 | 3 | 6 | 3 | 6 flavors, but the half-rule caps you at 3 |
Two ceilings are always in play: how much you're allowed to eat (n/2) and how much variety even exists (distinct count). You take whichever is smaller.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson