Problem Solving with JavaScript-Part 1 (Anagram)

In this series we will solve few common/uncommon problems using JavaScript with a different mindset (complexity and various ways to do it). For part 1, let’s start with a simple problem like Anagram.

Best way to solve anagram problem:

Anagram Examples

First let’s understand the problem,

To check whether 2 strings make an anagram, we will take a JavaScript function that will have 2 (or more) strings as arguments and it should return true if they have the same character instances, otherwise should return false.

For Example,

i) anagramChecker (Friend, Finder) => True

ii) anagramChecker (Race, Care) => True

iii) anagramChecker (Park, Tree) => False

iv) anagramChecker (Trap, Part) => True

v) anagramChecker (Draw, Drawing) => False

vi) anagramChecker (Height, Width) => False

Let’s think step by step towards the solution:

Step -1:

Whenever you have to compare strings, what comes to your mind first?
Yes you are right, length-check..
so let’s compare the length of 2 strings:

We will go ahead with the comparison only if length matches.

Step -2:

Now we have various paths from here:

i) Using loop (O(n²)):

One of my colleague suggested me the way, in which we directly start for loop to compare each and every instances of the string as below:

The above technique, will work efficiently if we have best-case strings scenario like : Height, Width -The loop will stop when character “e” won’t be present in the 2nd string.
However, take an example of strings “Part” and “Trap”, it will loop through 4 iterations to check that character “P” is present in the 2nd string or not.

The complexity of this will be n² due to 2 simultaneous for loop & find().

ii) Using string and array manipulation methods (O(n logn)):

We can write a generic solution that is easy to understand using split(), sort() and join() methods:

This solution’s complexity will be n log(n) due to Array.sort() operation.

iii) Using Objects Comparison (O(3n)):

We can convert both strings into object
e.g. anagramChecker(‘Trap’, ‘Part’) will firstly convert
‘Trap’=> {a: 1, p: 1, r: 1, t: 1} and ‘Part’ => {a: 1, p: 1, r: 1, t: 1}
and then compare those 2 objects:

The complexity of this will be 3(n) due to 3 for loops (2 for converting string into object and 1 for objects comparison).
However this will take a bit more space complexity, as we are converting string into objects. Thus, if we do not have space crunch this will be a best solution.

Time Complexity matrix graph notation

By looking at the graph, you might have understood that we can not choose solution 1 due to very high Time complexity. However, we can choose from the solution 2 and 3 according to the convenience and choice of complexity.

Please let me know which one suits you best and why in the comment section.

THANK YOU!!!