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?

Often, using a frequency counter will help to avoid using a nested loop, thus reducing the time complexity of our algorithm. Frequency counters can easily take an operation that would be O(N²) down to a much more palatable O(N). The reason that it can be applied to problems that arrays and strings specifically is because strings are considered array-like objects in JavaScript, therefore you can both access and perform operations on an index of a string with the exact same syntax you could use on an array.

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.

Edge Cases

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!