Problem Solving Patterns: Frequency Counter
One of the most helpful problem solving patterns in computer science is known as the frequency counter pattern. Commonly used on arrays and strings, it is named frequency counter because when we use it, we create an object or set to store the elements in our string or array, along with how many times they occur in that string or array. More specifically, the element is usually a key in the object, and the value for that key is how many times that element is found.
When should this pattern be used?
Frequency counters are most frequently(pun intended) used to compare data in some way. Some common problems I have seen on Leetcode where a frequency counter could be used are ones that compare different arrays or strings, such as checking whether two strings are anagrams of each other.
Why use this pattern?
Let’s solve a problem with a frequency counter
The problem I have chosen to solve is Leetcode problem 884: “Uncommon Words from Two Sentences.” This problem asks us to compare two sentences and return a list(in any order) of words that occur once in one of the sentences, but not at all in the other sentence.
If one or both of the sentences is empty, we need to plan accordingly. If both are empty, the return should be an empty array. If one of the sentences is empty, we return the other sentence but call “.split(‘ ‘)” on it, to ensure that it is returned as an array. I have found it extremely important to take these edge cases into consideration before diving into the heart of the problem, since there is almost nothing worse than spending a ton of time on what you think is a great solution and then realizing that your code needs to be completely refactored to deal with a couple of pesky edge cases.
Setting up the frequency counter
This is probably the easiest part. All that needs to be done is to declare a variable that is set equal to an empty object. I chose to call it ‘freqCounter’ to make it as demonstrative as possible.
Checking the frequency of each word
Now we will be adding words to the frequency counter object as keys. If the key already exists, the value(frequency) will increase by one. If the key does not exist, it will be added to the object and the value(frequency) will be set to one. We are going to iterate through each sentence using a for loop, but first we need to split the sentences into arrays where each element is a word in the sentence. Once we have done that, we can iterate through each sentence and adjust the frequency counter accordingly.
Finally, it is time to return the uncommon words
At this point, our frequency counter knows the frequency of every single word. That means that the only thing left to do is to return the words that are uncommon, or only occur once. The problem prompted us to return these words as an array, so the first thing to do is declare an empty array. I chose to name it uncommon. From there, we can iterate through our frequency counter to find the keys with a frequency value of one, and push those keys into our array of uncommon words before returning it.
Thank you so much for reading, and I hope that you found this article helpful!