Frequency Counter Pattern

Frequency Counter is one of the most frequent patterns in programming - if not the most. You will certainly use it in your side projects and work.

Let's use the classic anagram problem.

Anagram is a word/phrase created by rearranging the letter of another word/phrase. E.g., cat becomes act.

Instinctively, many devs write something like the following:

function isAnagram(str1, str2) {
  if (str1.length !== str2.length) return false;

  for (let i = 0; i < str1.length; i++) {
    let found = false;

  for (let j = 0; j < str2.length; j++) {
      if (str1[i] === str2[j]) {
        found = true;
        break;
      }
    }

    if (!found) return false;
  }

  return true;
}

We have big problems here:

• Nested loops: quadratic complexity - O(n²).

• The char frequency is not verified, making the solution inaccurate.

Instead, we can use the frequency pattern to know the occurrences for each char by just using Objects.

Here's the solution:

function isAnagram(str1, str2) {
    if (str1.length !== str2.length) {
        return false;
    }

    let frequencyObject1 = {};
    let frequencyObject2 = {};

    for (let i = 0; i < str1.length; i++) {
        frequencyObject1[str1[i]] = (frequencyObject1[str1[i]] || 0) + 1;
    }

    for (let i = 0; i < str2.length; i++) {
        frequencyObject2[str2[i]] = (frequencyObject2[str2[i]] || 0) + 1;
    }

    for (const key in frequencyObject1) {
        if (!(key in frequencyObject2)) return false;
        if (frequencyObject1[key] !== frequencyObject2[key]) return false;
    }

    return true;
}

Now, we have a better solution with a linear complexity - O(n).