Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Is An Anagram

Here is the interview question prompt, presented for reference.

Understanding Anagrams: A Simple Definition

An anagram is a fascinating literary device where you can rearrange the letters of a word, phrase, or name to form another meaningful sequence. Think of it as a jigsaw puzzle made of letters. For example, the word "cinema" can be rearranged to form "iceman."

The Challenge: Detecting Anagrams

Problem Statement

Given two input strings like "cinema" and "iceman," your task is to implement a method called isAnagram(str1, str2). This method should return true if the given strings are anagrams of each other and false otherwise.

Constraints to Consider

Computational Limits

  • The length of both input strings will be less than or equal to 100,000.

Character Rules

  • The input strings will only contain alphanumeric characters (a-z, A-Z, 0-9).

Performance Expectations

  • The expected time complexity for this operation is O(nlogn).
  • The expected space complexity is O(n).

Empty Strings are Valid

  • The input strings can be empty. Imagine that as a puzzle with no pieces; it's trivially solvable!

Coding the Solution

Given the constraints and expectations, you'll need to think carefully about your algorithm. The aim is not just to solve the problem, but to solve it efficiently within the given computational and space boundaries.

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

Challenges • Asked over 5 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.

Solved
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