Check if two string are anagram of each other

We will implement a simple algorithm in Javascript to check if the given two strings are anagram of each other or not. Everything will be written in ES6.

Anagram: An anagram of a string is another string that contains same characters, only the order of characters can be different.

Example

Input:
'prashant'
'tnahsarp'

'learnersbucket'
'tekcubsrenraes'

Output:
true
false

We will use different methods to solve this anagram strings problem.

  • Using sorting O(nlogn).
  • By counting the letters of strings O(n).

Using sorting.

Implementation

  • We will sort both strings in ascending order and check if they are equal.
  • If they are equal then return true else return false.
let anagramStrings = (str1, str2) => {

    //split the string to character array
    //sort the character array
    //then join the sorted array to form the string
    let sortedStr1 = str1.split('').sort().join('');
    let sortedStr2 = str2.split('').sort().join('');
    
    //return true if equal else return false
    return sortedStr1 === sortedStr2;
}
Input:
console.log(anagramStrings('prashant', 'tnahsarp'));
console.log(anagramStrings('learnersbucket', 'tekcubsrenraes'));

Output:
true
false

We have used string split() method to create the characters array.

Then using sort() method we have sorted the character array.

After that with join() we have joined the characters array to create the string.

Time complexity: O(nlogn).

Space complexity: O(n).

Time and Space complexity

  • We are using split() method to create the characters array which will take O(n). Then sorting the array will take O(nlogn) and to form the string again with join() will take O(n), so Time complexity is O(n + nlogn + n) = O(nlogn).
  • We are creating the character array from the given string which will take O(n + n), so Space complexity is O(n).

By counting the letters of the string.

Implementation

  • If both the strings are not equal then return false.
  • We will keep track of the characters in both the string and count their occurrences.
  • If all the characters count is equal then return true else return false.
let anagramStrings = (str1, str2) => {
    //if both the strings are not equal then return false
    if(str1.length !== str2.length){
      return false;
    }

    //create two objects to keep track
    let track = {};
    let track2 = {};
    
    //count the character occurrences of first string
    for(let i = 0; i < str1.length; i++){
        if(!track[str1[i]]){
           track[str1[i]] = 1;
        }else{
           track[str1[i]]++;
        }
    }

    //count the character occurrences of second string
    for(let i = 0; i < str2.length; i++){
        if(!track2[str2[i]]){
           track2[str2[i]] = 1;
        }else{
           track2[str2[i]]++;
        }
    }
    
    //check if the character occurrences in both the string are not equal then return false;
    for(let i = 0; i < str1.length; i++){
       if(track1[str1[i]] !== track2[str2[i]]){
          return false;
       } 
    }

    return true;

}
Input:
console.log(anagramStrings('prashant', 'tnahsarp'));
console.log(anagramStrings('learnersbucket', 'tekcubsrenraes'));

Output:
true
false

Time complexity: O(n).

Space complexity: O(n).

Time and Space complexity

  • We are counting the character occurrences of both the strings which will take O(n + n), Then check if count is equal or not in O(n), so Time complexity is O(n + n + n) = O(n).
  • We are keeping track of characters count, so Space complexity is O(n).

Comments

  • Method 4 (Bit Manipulation) The above implementation can be further optimized by using bit manipulation. If we start at a value of 0 and XOR all the characters of both strings, we should return an end value of 0 if they are anagrams because there would be an even occurrence of all characters in the anagram. Done forget to defend the code by validating inputs.

Leave a Reply

Your email address will not be published. Required fields are marked *