Hash-Based Counting And Canonicalization

What's being tested

These problems test hash-based counting and canonicalization: converting items to a normalized key and aggregating counts efficiently to answer pair/prefix queries. Interviewers probe correctness (edge cases), time/space complexity, and careful key design to avoid collisions or double-counting.

Patterns & templates

• Frequency map using a hashmap — count canonical keys in O(n) time and O(u) extra space, where u is unique canonical forms.

• Canonical key by transform — apply a deterministic transform (sorted digits, reversal-normalized string, trimmed prefix) before hashing to group equivalents.

• Use combination formula for pairs: for count k, number of unordered pairs is k*(k-1)/2 — avoid nested loops.

• Represent numeric canonical keys as strings when leading zeros matter; otherwise use integer tuples for compactness and faster hashing.

• Streaming accumulation: update counts on the fly, emit pairs incrementally with current count to save memory when needed.

• For prefix problems, build a prefix-hash map or use a trie when many shared prefixes reduce key space; O(L*n) where L is average length.

Common pitfalls

Pitfall: Forgetting leading zeros — treating reversed digits as integers collapses distinct forms like "010" and "10".

Pitfall: Miscounting pairs by summing k instead of using k*(k-1)/2, producing linear instead of combinatorial results.

Pitfall: Creating heavy keys (e.g., full sorted strings) for very long items when a fixed-length hash or tuple would suffice, increasing memory and hash time.

Practice these

the practice cards below cover the canonical variants — solve all of them and time yourself