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

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 min of the two tallies for cows.
• Longest Harmonious Subsequence — count values; for each v, combine count[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

1. Two tally tables. For Bulls and Cows or the anagram problem, draw both frequency tables and read the answer off the per-letter differences.
2. 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.