Arrays and Hashing
Counting instead of comparing
When order does not matter, a count is the whole content of the input.
Key idea
The idea
A set forgets how many times it saw something. Often that count is exactly what the problem is about. A dict from value to count, sometimes called a multiset or a frequency map, keeps it.
Building one takes three lines. The .get(key, 0) call is what saves you from checking whether the key exists yet.
Counting down, not just up
The second half of the technique is spending a count rather than building one. Here is the useful question it answers: can you build a message out of the letters available in a magazine, using each letter at most as many times as it appears?
Why it works
Why counting down matters
"noon" fails because it needs two o's and only one is available. A version that merely checked whether each letter appears somewhere would wrongly say yes.
Building up then spending down is the shape underneath a large family of problems, and it is exactly what a sliding window does in Unit 3: add the character entering the window, subtract the one leaving.
Tip
The tools that do this for you
Counter(items) builds the frequency map in one call. Two frequency maps compare equal when they hold the same items with the same counts, and dict comparison ignores insertion order, so two collections that hold the same things in a different order come out equal.
Sorting is the other common way to compare two collections while ignoring order. It is O(n log n) against counting's O(n), and it is worth naming in an interview as the obvious alternative before you say why you are not using it.
Edge cases
What the constraints let you assume
Counting problems on text often promise lowercase English letters only. That promise lets you swap the dict for a fixed 26-slot list, which makes the space O(1) rather than O(n) because 26 does not grow with the input.
Check whether the promise is actually made before relying on it, and say which assumption you are taking. The follow-up question is almost always what happens if the input is Unicode, and the answer is that you go back to a dict.
The family of questions this answers
Once the count map is the object you are reasoning about, a lot of different-sounding questions become one line each. Are these two collections the same? Equality. Does one fit inside the other? Every count on the left is at most the matching count on the right. What is left over? Subtraction.
None of these need a new technique. They need you to notice that the count map is the real object, and that the question is asking something about the relationship between two of them.
Tip
Counter subtraction drops negatives
pantry - recipe keeps only positive counts, which is what you want when asking what is left over, and quietly wrong when you wanted a signed difference. When you need both directions, compute the other subtraction too, or compare the maps key by key.
Build the frequency map yourself
Write these without importing Counter, since the point is the loop. frequencies returns a plain dict of counts. times_buildable asks how many complete copies of a word you could make from a pile of letters. most_frequent returns the value with the highest count, breaking ties toward whichever value reached that count first.
Tests
print(frequencies("banana"))
print(times_buildable("ab", "aabb"), times_buildable("ab", "aab"), times_buildable("ab", "aaa"))
print(most_frequent([1, 2, 2, 3, 3]))
print(most_frequent([]))Output
Run the tests when you are ready.
Valid Anagram
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.