Interview Question : Check If Two Strings Are Anagrams

Today I am gonna share with you a programming question that I encountered in one of my interviews for the Frontend Software Engineer position that is how can we check if two strings are anagrams.
Anagrams are words that have same and equal amount of letters but they can have different order. For example.
abc is anagram of cba, bac, bca and acb
You can read more about anagrams here
We will be using JavaScript for our solution today but feel free to follow along in any programming language.

Sort Solution

The easiest method to check if two words are anagrams is to sort both the words and then compare them. If both words are equal then the words are anagrams. Here is an example

function isAnagramUsingSort(firstWord, secondWord) {
  let firstSorted = firstWord.
                    split('').
                    sort().
                    join('');
  let secondSorted = secondWord.
                    split('').
                    sort().
                    join('');
  return firstSorted === secondSorted;
}

Sorting algorithms are usually very expensive and usually have exponential complexity so this solution is utterly useless and should not be used.

HashMap Solution

In this solution we generate HashMaps of both words and then compare them to determine if the words are anagrams. Here are some examples of HashMaps
abc = { a: 1, b: 1, c: 1 }
abca = { a: 2, b: 1, c: 1 }
bca = { b: 1, c: 1, a: 1 }
After generating these HashMaps we can simply check if the every letter exists in both HashMaps and is occurred the same amount of times like in our example above abc and bca have the same letters as well as the same number of letters in there HashMaps, so they are anagrams.

Here is the code example.

function isAnagramUsingHashMap(firstWord, secondWord) {
  if (firstWord.lenght !== secondWord.lenght) {
    return false;
  }
  const firstMap = {};
  const secondMap = {};
  // Generating Hashmaps
  for (let i=0; i<firstWord.length; i++) {
    const firstWordLetter = firstWord[i];
    const secondWordLetter = secondWord[i];
    firstMap[firstWordLetter] = 
      firstMap[firstWordLetter] 
        ? firstMap[firstWordLetter] + 1 
        : 1; 
    secondMap[secondWordLetter] = 
      secondMap[secondWordLetter] 
        ? secondMap[secondWordLetter] + 1 
        : 1;
  }
  // Comparing Hashmaps
  for (let i=0; i<firstWord.length; i++) {
    const letter = firstWord[i];
    if (firstMap[letter] !== secondMap[letter]) {
      return false;
    }
  }

  return true;
}

This is a decent solution that has a complexity of O(2n).

Letter Encoding Solution

We can improve our HashMap algorithm if we encode the letters to prime numbers. Prime numbers are number which are only divisible by 1 and them self e.g. 2, 3, 5, 7, 11 and so on.
Prime numbers have a unique property that is if you were to multiply any two prime numbers, Their product will always be unique and different from the product of any other prime numbers. For example consider the following examples
2 x 3 = 6
3 x 5 = 15
5 x 7 = 35
3 x 7 = 21
You can see that all the above multiplications result in unique numbers.
We can use this property of prime numbers to our advantage by assigning a prime number to every alphabet and then multiplying the encoded numbers together to get the product. The unique thing about this product will be that it will be unique for every set of words which are not anagrams i.e. they have different letters. Here are a few examples
abc = 2x3x5 = 30
abd = 2x3x7 = 42
aad = 2x2x7 = 28
As you can see that the product is different in all the above cases. Once we get this product of both words we can simply compare the products and tell if the words are anagrams. Here is the code for this solution

function isAnagramUsingEncoding(firstWord, secondWord) {
  if (firstWord.lenght !== secondWord.lenght) {
    return false;
  }
  const alphabets = {
    a: 2, b: 3, c: 5, d: 7,
    e: 11, f: 13, g: 17, h: 19,
    i: 23, j: 29, k: 31, l: 37,
    m: 31, n: 43, o: 47, p: 53,
    q: 59, r: 61, s: 67, t: 71,
    u: 73, v: 79, w: 83, x: 89,
    y: 97, z: 103,
  };
  let firstWordProduct = 1;
  let secondWordProduct = 1;
  for (let i=0; i<firstWord.length; i++) {
    firstWordProduct = firstWordProduct * alphabets[firstWord[i]];
    secondWordProduct = secondWordProduct * alphabets[secondWord[i]];
  }
  return firstWordProduct === secondWordProduct;
}

This solution has O(n) complexity and is the most performant solution of all.

Can you improve the above solutions ? Please let me know in the comments below. If you have other solutions to this problem, share in the comments.