What is the frequency counting pattern, and what kinds of problems does it solve?
The frequency counting pattern is a way of solving problems where you need to know how many times each thing appears. You make a dictionary, you walk through the data once, and for every item you add one to its count.
counts = {}
for item in items:
counts[item] = counts.get(item, 0) + 1
So what kinds of problems does it solve? Here are the common ones. Finding a duplicate. Finding the item that appears most often. Finding the item that appears exactly once. Counting how many times each word appears in a sentence. Grouping items that share a property. And deciding whether two lists hold the same letters with the same counts.
And what do all of those have in common? Each one needs a number attached to each item, and each one needs the counts to be right before the answer can be worked out. That is exactly what the pattern gives you.
the problem the thing you keep
------------------------------ ----------------------------
is there a duplicate? the set of things you have seen
what appears most often? the count of each thing
what appears exactly once? the count of each thing
group by a property the list of things per key
So the pattern has three steps, and they are always the same. You make the empty dictionary. You walk through the data and update the count for each item. And then you look through the dictionary for the answer, whether that is the biggest count, the count of one, or the number of items with a count above one.
There is one thing to watch out for. The count has to be built completely before you start looking for the answer, because the last item in the list might be the one that appears most often. So if the question is about the biggest count, you need two passes over the data, one to count and one to find the biggest.
So the rule to remember is this. When a question asks how many times something happens, count it first and decide afterwards.
The last question in this topic shows the pattern on a sentence.