Algorithm Series — the Frequency Counter Pattern

After doing several coding challenges, you’ll notice similarities between some of them. There are certain problem solving patterns we can use to approach each challenge based on what they’re asking us to do. While there is definitely value in thinking through the problem on your own and just making it work first, we can use these problem solving patterns as tools to solve the challenges more effectively. The pattern we’ll be focusing on in this article will be the “frequency counter” pattern.

What is the frequency counter pattern?

While not an official name or computer science term, the problem will most likely ask if your inputs will have the same count for each value in them or ask if one input is a variation of the other. A strategy we can use to approach this pattern is by using an object and setting the keys as the value we are counting, and the value will be the actual count. We’ll go through an example from Colt Steele’s Javascript Algorithms & Data Structures course.

Example 1: Anagram

Write a function that takes in two strings as arguments and determines if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, so ‘desserts’ would be an anagram of ‘stressed’.

//test cases for our function 
validAnagram('stressed', 'desserts') // true
validAnagram('nope', 'notanagram')// false
validAnagram('pup', 'puppy')// false
validAnagram('listen', 'silent') // true

In this problem, we want to make sure both words we are passing in are the same length and have the same frequency for each character. We know if our strings are different lengths there is no way for them to be anagrams of each other, so we can start off our function with the conditional statement below.

function validAnagram(word1, word2){
  if (word1.length !== word2.length){
      return false
  }

}

Next we want to have two separate variables to hold our objects that will count how many of each letter is in the corresponding word. We’ll loop through each word separately to set each unique letter as their related object’s keys and their values to 1 if they’re not in our counter yet, and add 1 to the value if the letter is already in our counter object.

function validAnagram(word1, word2){
  if (word1.length !== word2.length){
      return false
  }
  
  let letterCounter1 = {}
  let letterCounter2 = {}
  
  for (const letter of word1){
      letterCounter1[letter] = (letterCounter1[letter] || 0) + 1
  }
  for (const letter of word2){
      letterCounter2[letter] = (letterCounter2[letter] || 0) + 1
  }
  
}

With our first test case example of validAnagram(‘stressed’, ‘desserts’) our letterCounter1 object and letterCounter2 object would look like this:

//visualization purposes only 
letterCounter1 = {
  s: 3,
  t: 1,
  r: 1,
  e: 2,
  d: 1
}
letterCounter2 = {
  d: 1,
  e: 2,
  s: 3,
  r: 1,
  t: 1
}

Now that we have our letterCounter objects with their letters and count values, we need to check if the values for each letter match one another!

We’ll loop over one of our letterCounter objects and have a condition to return false if the frequency of one of the letters is not equal to the frequency of it in the other letterCounter object. If we make it through the whole loop without hitting this condition, our words are anagrams and will return true!

Our final solution will look something like this.

function validAnagram(word1, word2){
  if (word1.length !== word2.length){
      return false
  }
  
  let letterCounter1 = {}
  let letterCounter2 = {}
  
  for (const letter of word1){
      letterCounter1[letter] = (letterCounter1[letter] || 0) + 1
  }
  for (const letter of word2){
      letterCounter2[letter] = (letterCounter2[letter] || 0) + 1
  }
  for (const letter in letterCounter1){
      if (letterCounter1[letter] !== letterCounter2[letter]){
        return false
      }
  }
    return true
}

The function will have a time complexity of O(n) since we are looping through our inputs separately and the speed will vary based on the length of the words passed in.

I understand there are multiple ways we can approach this problem solving pattern, but this is just one way to solve it. If you know of a better or different way to approach the frequency counter problem or any other suggestions, please leave me a comment! I love learning different approaches to the same problem or how we can construct a more efficient solution!

Thanks for reading and happy coding!

Mars