Counting With Maps: Same Letters, Top Items
In a word game, two players each build a word from a pile of letter tiles, and a referee must check whether both words used exactly the same tiles. The letters can be in any order, but every tile has to be accounted for. When order stops mattering, the only thing left to compare is how many of each.
The rule
When order doesn't matter, compare counts, not sequences.
A dictionary from item to count captures everything about a collection except its order. Python's Counter builds one in a single call, and two Counters compare equal exactly when every item appears the same number of times in both:
from collections import Counter
def same_tiles(a, b):
if len(a) != len(b):
return False # different sizes can never match
return Counter(a) == Counter(b)Sorting both words and comparing (sorted(a) == sorted(b)) also works, because sorting puts equal letters together. It costs n log n instead of n, which is usually fine; counting is simply the more direct statement of the idea.
Counting is also the first half of every "most frequent" question. To find the k most common tags on a blog, count them, then pick the biggest counts:
tags = ["py", "js", "py", "go", "py", "js", "rs"]
Counter(tags).most_common(2) # [('py', 3), ('js', 2)]When interviewers want better than sorting the counts, use buckets: a count can never exceed the number of items n, so make a list of n + 1 buckets, drop each tag into the bucket for its count, and read buckets from the top down. That is one pass to count and one pass to read.
The shortcut
Keep one tally, up for the first word and down for the second. If every count lands back on zero, the tiles matched. You never need two dictionaries, and you can stop the moment a count goes below zero, because the second word just used a tile the first never had.
Quick reject
Both have 5 letters, so keep going. Different lengths would have ended it here.
The trap is comparing sets. set("aab") == set("abb") is True, because a set records only which letters appear, not how many times. Counting keeps the "how many".
Drills
Answer fast — trust the rule.
What is Counter("aab") == Counter("abb")?
Which check can answer "not the same tiles" before any counting at all?
What does Counter(["py", "js", "py", "go", "py", "js", "rs"]).most_common(2) return?
In the bucket trick for the k most frequent items, why can each count be used as a list index?
Remember
- When order doesn't matter, compare counts, not sequences.
- Shortcut: one tally, up for the first, down for the second; all zeros means a match.
- Trap: comparing sets, which forget how many times each item appears.