Interview Question: Are two strings anagrams?

This article is the first post of a series where we will solve common code interview questions using different ways in JavaScript.

If you have some experience in applying for programming jobs, you would know that there would at least be one (generally more) string based simple question asked in initial rounds.

One of those common questions is “Write a function to check if two strings are anagrams or not”. Let us try to understand what this problem is and how might we solve it.

What are anagrams?

One string is an anagram of another if it uses the same characters in the same quantity. That is, we should be able to re-arrange characters in one of the string to get other one.

For the purpose of this solution we will consider –

• Strings contain only characters, not spaces or special characters.
• Consider capital letters to be the same as lower case.

Some valid examples of anagrams (we will treat these as our test cases) –

• Elbow, Below
• State, Taste
• Night, Thing
• The eyes! , They see

Let us also consider a few negative scenarios. Below are not anagrams

• State, Tastes
• Tried, Diet

Let us see various ways of solving this specific problem and the complexity of each approach.

For both the solutions we are going to use a simple regex to remove special characters and spaces from our input string.

str.replace(/[^\w]/g,"")

The regular expression in above line tells JavaScript to remove every non-word(\w) from the string.

Solution 1 – Sort and compare

This is a very easy and simple way of tackling this problem. We first sort both the strings using Array.sort() method and then compare both the strings. If true then they are anagrams else not.

function anagrams(str1, str2) {
    str1 = removeExtraCharsAndConvertToLowerCase(str1);
    str2 = removeExtraCharsAndConvertToLowerCase(str2);

    return sortString(str1) === sortString(str2);
}

function sortString(string) {
    return string.split('').sort().join('');
}

function removeExtraCharsAndConvertToLowerCase(str) {
    return str.replace(/[^\w]/g, "").toLowerCase();
}

This solution uses in-built sort method which internally uses merge sort, thus making the complexity of our solution to be O(nlogn).

Solution 2 – Compare character map and length

Like string based questions are very common in coding interviews, creating a character map to solve many of those problems is also a common technique. This solution uses this technique to solve our problem in O(n) time.

We first remove spaces and special characters from our strings and then create character maps for these strings.

Once character maps are created, we want to compare that the size of both character maps is same and that the value for each character in both maps is also same.

Sample character map for Elbow and Below ->

Elbow – {“e”:1,”l”:1,”b”:1,”o”:1,”w”:1}

Below – {“b”:1,”e”:1,”l”:1,”o”:1,”w”:1}

function anagrams(str1, str2) {
    const str1CharMap = createCharMap(removeExtraCharsAndConvertToLowerCase(str1));
    const str2CharMap = createCharMap(removeExtraCharsAndConvertToLowerCase(str2));
    if (Object.keys(str1CharMap).length !== Object.keys(str2CharMap).length) return false;
    for (let key in str1CharMap) {
        if (str1CharMap[key] !== str2CharMap[key]) return false;
    }
    return true;

}

function removeExtraCharsAndConvertToLowerCase(str) {
    return str.replace(/[^\w]/g, "").toLowerCase();
}

function createCharMap(str){
    let charMap = {};
    for (let char of string) {
        charMap[char] = charMap[char] + 1 || 1;
    }
    return charMap;
}

/* Use this method to create character map if 
you would like to show your knowledge of reduce 
function */
// function createCharMap(str) {
//     return str.split('').reduce((map, c) => { map[c] = map[c] + 1 || 1; return map; }, {});
// }