Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Is An Anagram

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?

Constraints

  • 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

Martti Commented on Jul 04, 2019:

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).

Martti Commented on Jul 05, 2019:

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.

Leon Commented on Jul 06, 2019:

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.

Martti Commented on Jul 06, 2019:

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

Minh Nguyen Commented on Feb 02, 2020:

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?

Ray Commented on Jan 25, 2021:

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