Anagram Algorithm using the Frequency Counter method

An anagram is a word or phrase formed by rearranging the letters of another word or phrase. In other words, it's a type of wordplay where the letters of a word or phrase are rearranged to create a new word or phrase that has a different meaning. Here are some examples:

• "listen" and "silent"
• "elbow" and "below"
• "night" and "thing"
• "debit card" and "bad credit"
• "astronomer" and "moon starer"

isAnagram(str1, str2)

This function accepts two parameters, both strings, and will only contain lowercase letters and spaces.
The spaces should not be counted as characters for the anagram but will be present.
The return value for this function should always be a boolean.
you can expect two empty strings but never null values.

Examples

isAnagram("", "")                      // Return: true
isAnagram("aab", "abb")                // Return: false
isAnagram("night", "thing")            // Return: true
isAnagram("qwerty", "qeywrt")          // Return: true
isAnagram("zxcvbnm", "zxccvbnm")       // Return: false
isAnagram("astronomer", "moon starer") // Return: true

Let's break it down!

We need to compaire two strings to see if they have the same characters and same frequency of use for those characters.
This is because an anagram uses the same exact letters from the first word to form another.
Let's use "astronomer" as an example and split the word into it's characters and their frequency

{
  "a": 1,
  "e": 1,
  "m": 1,
  "n": 1,
  "o": 2,
  "r": 2,
  "s": 1,
  "t": 1
}

Now that we can see the frequency of astronomer, let's take a look at "moon starer"
I've removed the space since we will be ignoring them for the algorithm.

{
  "a": 1,
  "e": 1,
  "m": 1,
  "n": 1,
  "o": 2,
  "r": 2,
  "s": 1,
  "t": 1
}

These two words would be considered an anagram because each letter of astronomer exists in "moon starer" at the same frequency.
Let's break down another!

This time let's break down "zxcvbnm"

{
  "z": 1,
  "x": 1,
  "c": 1,
  "v": 1,
  "b": 1,
  "n": 1,
  "m": 1
}

Pretty easy to see the frequency here, but let's break down "zxccvbnm"

{
  "z": 1,
  "x": 1,
  "c": 2,
  "v": 1,
  "b": 1,
  "n": 1,
  "m": 1
}

All the letters from "zxcvbnm" are present in "zxccvbnm" but not at the same frequency.
This would not be considered an anagram!

Pseudo Code

Now that we understand the task at hand, lets start some pseudo coding!

First off, if the two strings are exactly the same, then they are anagrams.

// if the strings are exactly the same, return true

We know that there might be spaces in the string passed through.
We will need to make sure we remove these spaces as we don't want them to count towards our character counts.

// if the strings are exactly the same, return true
+// remove spaces from each string

Once the spaces are removed, we can start comparing the two strings.
To do this we are going to use the frequency counter method of problem solving.
The way we can implement this method is by counting how many times a character shows up in the two strings seperatly.
Then comparing them at the end to make sure they are the same frequency.

First we will start by declaring the two frequency counter variables.

// if the strings are exactly the same, return true
// remove spaces from each string
+// define two frequency counter variables to keep track of the present letters.

Now, we will need to loop over the first string and count the frequency of each character.
The logic here should first check if the character already exists in the frequency counter variable
If the character exists, that means we have started counting this character already and we just need to increment it.
If the character does not exist in the frequency counter variable then it is the first time we are encountering this character.
So, in this case we set the characters value to 1 within the frequency counter variable.

// if the strings are exactly the same, return true
// remove spaces from each string
// define two frequency counter variables to keep track of the present letters.
+// loop over the first string
+  // if the character exists in the first frequency counter variable, increment the counter
+  // If the character doesn't exist in the first frequency variable, add it with a value of 1

Now that the first string has been counted, let's repeat this for the second string.
The pseudo code here will be almost identical except for one extra piece of logic.
If a character in string 2 does not exist in string 1 then that would not be an anagram.

// if the strings are exactly the same, return true
// remove spaces from each string
// define two frequency counter variables to keep track of the present letters.
// loop over the first string
  // if the character exists in the first frequency counter variable, increment the counter
  // If the character doesn't exist in the first frequency variable, add it with a value of 1
+// loop over the second string
+  // If the character doesn't exist in the first frequency counter, return false
+  // If the character exists in both counters, increment the second counters value
+  // If the character exists in the first but not the second frequency counter, add if to the second with a value of 1

Cool! We've counted both strings characters and we just need to compare them to eachother.
To do this we can loop over this first frequency counter variable and compare it to the second.
If the counts don't match up to eachother, we know this is not an anagram.

// if the strings are exactly the same, return true
// remove spaces from each string
// define two frequency counter variables to keep track of the present letters.
// loop over the first string
  // if the character exists in the first frequency counter variable, increment the counter
  // If the character doesn't exist in the first frequency variable, add it with a value of 1
// loop over the second string
  // If the character doesn't exist in the first frequency counter, return false
  // If the character exists in both counters, increment the second counters value
  // If the character exists in the first but not the second frequency counter, add if to the second with a value of 1
+// Loop over the first frequency counter
+  // If the cound for the character is different between both counters, return false.

Finally, if the loop completed without finding a discrepency, this is in fact an anagram and we can return true.

// if the strings are exactly the same, return true
// remove spaces from each string
// define two frequency counter variables to keep track of the present letters.
// loop over the first string
  // if the character exists in the first frequency counter variable, increment the counter
  // If the character doesn't exist in the first frequency variable, add it with a value of 1
// loop over the second string
  // If the character doesn't exist in the first frequency counter, return false
  // If the character exists in both counters, increment the second counters value
  // If the character exists in the first but not the second frequency counter, add if to the second with a value of 1
// Loop over the first frequency counter
  // If the cound for the character is different between both counters, return false.
return true;

Let's code!

With the logic outlined in pseudo code, we code this algorithm.
The first logic is simple in that it just compares the two strings.

function isAnagram(str1, str2) {
  // if the strings are exactly the same, return true
  if (str1 === str2) return true; // inline if statement for style
}

Next, let's remove the potential spaces from both strings and declare our frequency counter variables.

function isAnagram(str1, str2) {
  if (str1 === str2) return true; // inline if statement for style

  // remove spaces from each string
  const evaluationString1 = str1.replace(/\s/g, ""); // This regex matches any white spaces with the \s metacharacter
  const evaluationString2 = str2.replace(/\s/g, ""); // and replaces them with nothing.

  // define two frequency counter variables to keep track of the present letters.
  let frequencyCounter1 = {}; // Using an object here for easy key: value evaluation of characters
  let frequencyCounter2 = {};
}

Now, let's loop over the first string and count the characters.

function isAnagram(str1, str2) {
  if (str1 === str2) return true; // inline if statement for style

  const evaluationString1 = str1.replace(/\s/g, ""); // This regex matches any white spaces with the \s metacharacter
  const evaluationString2 = str2.replace(/\s/g, ""); // and replaces them with nothing.

  let frequencyCounter1 = {}; // Using an object here for easy key: value evaluation of characters
  let frequencyCounter2 = {};

  // loop over the first string
  for (let i = 0; i < evaluationString1.length; i++) {
      const character = evaluationString1[i];
      if (frequencyCounter1[character]) { // Checking if the character has already been counted with a truthy statement
          // if the character exists in the first frequency counter variable, increment the counter
          frequencyCounter1[character]++;
      } else {
          // If the character doesn't exist in the first frequency variable, add it with a value of 1
          frequencyCounter1[character] = 1;
      }
  }
}

Duplicate this for the second string add the logic to check if the letter exists in the first string.

function isAnagram(str1, str2) {
  if (str1 === str2) return true; // inline if statement for style

  const evaluationString1 = str1.replace(/\s/g, ""); // This regex matches any white spaces with the \s metacharacter
  const evaluationString2 = str2.replace(/\s/g, ""); // and replaces them with nothing.

  let frequencyCounter1 = {}; // Using an object here for easy key: value evaluation of characters
  let frequencyCounter2 = {};

  for (let i = 0; i < evaluationString1.length; i++) {
      const character = evaluationString1[i];
      if (frequencyCounter1[character]) { // Checking if the character has already been counted with a truthy statement
          frequencyCounter1[character]++;
      } else {
          frequencyCounter1[character] = 1;
      }
  }
  // loop over the second string
  for (let i = 0; i < evaluationString2.length; i++) {
      const character = evaluationString2[i];
      if (!frequencyCounter1[character]) { // Checking if the character is in the first string with a falsy 
          // If the character doesn't exist in the first frequency counter, return false
          return false;
      } else if (frequencyCounter2[character]) {
          // If the character exists in both counters, increment the second counters value
          frequencyCounter2[character]++
      } else {
          // If the character exists in the first but not the second frequency counter, add if to the second with a value of 1
          frequencyCounter2[character] = 1;
      }
  }
  
}

Finally, let's check if the two frequency counts are the same

function isAnagram(str1, str2) {
  if (str1 === str2) return true; // inline if statement for style

  const evaluationString1 = str1.replace(/\s/g, ""); // This regex matches any white spaces with the \s metacharacter
  const evaluationString2 = str2.replace(/\s/g, ""); // and replaces them with nothing.

  let frequencyCounter1 = {}; // Using an object here for easy key: value evaluation of characters
  let frequencyCounter2 = {};

  for (let i = 0; i < evaluationString1.length; i++) {
      const character = evaluationString1[i];
      if (frequencyCounter1[character]) { // Checking if the character has already been counted with a truthy statement
          frequencyCounter1[character]++;
      } else {
          frequencyCounter1[character] = 1;
      }
  }
  for (let i = 0; i < evaluationString2.length; i++) {
      const character = evaluationString2[i];
      if (!frequencyCounter1[character]) { // Checking if the character is in the first string with a falsy 
          return false;
      } else if (frequencyCounter2[character]) {
          frequencyCounter2[character]++
      } else {
          frequencyCounter2[character] = 1;
      }
  }
  
  // Loop over the first frequency counter
  for (let character in frequencyCounter1) {
      // If the cound for the character is different between both counters, return false.
      if (frequencyCounter1[character] !== frequencyCounter2[character]) return false
  }
  return true;
}

We now have an algorith to check if two strings are anagrams!