DEV Community

Cover image for JS Anagrams with Big O Notation
Anas Nabil
Anas Nabil

Posted on • Edited on

JS Anagrams with Big O Notation

#javascript #tutorial #algorithms #programming

We say that two strings are anagrams of each other if they have the exact same letters in same quantity of existance of each letter, regardless of non-alphabetic letters and case sensitivity.

Here's an example

// 'hello', 'elloh' -> anagrams // 'love', 'hate' -> not anagrams // 'i'm 26 years old' -> 'myeald oirs o' -> anagrams
Enter fullscreen mode Exit fullscreen mode

Well, the Solution is Simple

We just need to remove all non-alphabetic letters first, and turn all letters into lower case.

// 'Hello World!@# ---30..' -> 'helloworld30' const inputString = 'Hello World!@# ---30..' inputString.toLowerCase().replace(/[\W_]+/g, ''); // returns 'helloworld30'
Enter fullscreen mode Exit fullscreen mode

\W leaves the underscore, A short equivalent for [^a-zA-Z0-9] would be [\W_]

Then we need to convert string to array, sort the array alphabetically, and then turn it back into a string

// 'hello' -> ['h', 'e', 'l', 'l', 'o'] -> ['e', 'h', 'l', 'l', 'o'] -> ehllo const inputString = 'Hello World!@# ---30..' inputString.toLowerCase().replace(/[\W_]+/g, '').split('').sort().join(''); // returns '03dehllloorw'
Enter fullscreen mode Exit fullscreen mode

Here's the final code

const anagrams = (firstInput, secondInput) => { return ( firstInput .toLowerCase() .replace(/[\W_]+/g, '') .split('') .sort() .join('') === secondInput .toLowerCase() .replace(/[\W_]+/g, '') .split('') .sort() .join('') ); }
Enter fullscreen mode Exit fullscreen mode

Big-O Complexity Chart

Big O Notation
Time Complexity: O(n * Log n) because we've used sort algorithm

However, a Better solutions do exist, We'll also write another solution

const anagrams = (firstInput, secondInput) => { firstInput = firstInput.toLowerCase().replace(/[\W_]+/g, ''); secondInput = secondInput.toLowerCase().replace(/[\W_]+/g, ''); if (firstInput.length !== secondInput.length) { return false; } const inputLetterCount = {}; for (let i = 0; i < firstInput.length; i++) { const currentLetter = firstInput[i]; inputLetterCount[currentLetter] = inputLetterCount[currentLetter] + 1 || 1; } for (let i = 0; i < secondInput.length; i++) { const currentLetter = secondInput[i]; if (!inputLetterCount[currentLetter]) return false; else inputLetterCount[currentLetter]--; } return true; };
Enter fullscreen mode Exit fullscreen mode

Big O Notation
Time Complexity: O(n)
Space Complexity: O(1)

Happy Coding ❤

Top comments (1)

Collapse
 
emiifont profile image
Emilio Font • • Edited

you can also count the letters in a fixed length array. for e.g:

`
let d = "hello";
let k = "holle";
const arr = new Array(26).fill(0);
const arr2 = new Array(26).fill(0);

for(let i = 0; i < d.length; i++) {
arr[d[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
arr2[k[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}

return arr.join(",") === arr2.join(",")
`