Here is the interview question prompt, presented for reference.

Here's the definition of an anagram: *a word, phrase, or name formed by rearranging the letters of another: such as cinema, formed from iceman.*

We are given two strings like "cinema" and "iceman" as inputs. Can you write a method `isAnagram(str1, str2)`

that will return `true`

or `false`

depending on whether the strings are anagrams of each other?

- Length of both the strings <=
`100000`

- The strings will contain only alphanumeric characters (
`a-z , A-Z, 0-9`

) - The strings can be empty
- Expected time complexity :
`O(nlogn)`

- Expected space complexity :
`O(n)`

You can see the full challenge with visuals at this link.

**Challenges**
â€¢ Asked about 2 years ago by Jake from AlgoDaily

Since the previous challenge already mentioned time complexities. It should be mentioned that the sorting solution is Quasilinear O(n log n) and a linear solution exists.

If you create a set from both strings O(n+m) and then check that both strings are subsets of each other O(n+m) you can check for anagrams in linear time O(n).

Admittedly JS doesn't allow you to succinctly check set equality, so you'd have to write the loops yourself. It would probably be better just to use the example 3 liner.

Set doesn't work, see Leon's comment.

**Edit:** Counting is necessary, so a dictionary of elements as keys and number of occurrences as values, should still allow for linear time assuming inserts are O(1).

Since the previous challenge already mentioned time complexities. It should be mentioned that the sorting solution is Quasilinear O(n log n) and a linear solution exists. If you create a set from both strings O(n+m) and then check that both strings are subsets of each other O(n+m) you can check for anagrams in linear time O(n).

Admittedly JS doesn't allow you to succinctly check set equality, so you'd have to write the loops yourself. It would probably be better just to use the example 3 liner.

The solution with `Set`

assumes that there are no duplicate letters, but what if there are? Moreover, if it's a phrase and not just a single word you might have multiple spaces.

you're right, you would need a hashmap to store the number of occurrences of an element.

Well, there is one problem with python2 which is using to run code/run tests in your server.

When I check a character in a string, it checks for "case insensitive" instead!

I'd like to run my code against python v3. How do I do it?

Shouldn't there be an O(n) time complexity solution to this? How about creating a Map for each string then loop through each character in one of the Maps w/ the other? You can check that lengths of each string are the same first, otherwise return false. The Space Complexity would be O(n).

for ( let char in mapChar1 ) {

if ( mapChar1[ char ] !== mapChar2[ char ]) return false

}

return true