``````# Algorithm to determine if two strings are an anagram
> The anagram test is commonly used to demonstrate how an naive implementation can perform significant order of magnitudes slower than an efficient one.
> A word is an anagram of another if you can rearrange its characters to produce the second word. Here we write a function that given two strings determines if they are anagrams of each other.

```js
/**
* A word is an anagram of another if you can rearrange its characters to produce the second word.
* Given two strings determine if they are anagrams of each other.
* - 'earth' and 'heart' are anagrams
* - 'silent' and 'listen' are anagrams
* - 'foo' and 'bar' are not anagrams
*/
```

* We will start by creating our areAnagrams function

```js
export function areAnagrams(s1: string, s2: string): boolean {
}
```
A plain implementation that derives from the definition would be to
* check all the permutations of s1
* and then see if it is equal to s2
* If they are then the strings are anagrams
* If no permutation matched then they are not anagrams

```js
export function areAnagrams(s1: string, s2: string): boolean {
for (const permutation of permutations(s1)) {
if (permutation === s2) return true;
}
return false;
}
```
***Select the for line***
* Although such an implementation would work, in this case the complexity of the algorithm will be equal to possible permutations of s1, so order of n! (where n is the number of characters in the string).

***Select the first line of the requirements***
* If you read into the requirements you can realize that instead of doing actual re-arrangments you simply need to check if they have *exactly* the same characters.

***Delete the function body***
One quick way of checking the equality between two sets of characters in strings is simply to
* break the strings into their characters, sort them, and join them again.
* we do the same for the second strings.
* finally we check if the strings are equal.
* if these sorted character strings are equal then the original strings were anagrams.

```js
s1 = s1.split('').sort().join('');
s2 = s2.split('').sort().join('');
return s1 === s2;
```

***Select the sort function***
* The complexity in this case will be driven by the sort function which is of the order `nLogn`. We can do better.

***Delete the function body***
* A better way to make sure that the strings have the same characters is to simply use a HashMap that counts the characters between the two strings and makes sure this count per character is the same between the strings

```js
export function areAnagrams(s1: string, s2: string): boolean {
const charCount = new Map<string, number>();
for (const char of s1.split('')) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
for (const char of s2.split('')) {
if (!charCount.has(char)) return false;
charCount.set(char, charCount.get(char) - 1);
}
return Array.from(charCount.values()).every(val => val === 0);
}
```
* We start by creating a map to track this character count. We initialize it to a map with string keys and number values.
* We go ahead and iterate through all the characters in string 1.
* For each character in string 1
* We set the character count for this character.
* We get the previous value, If there was no previous value we initializing it to 0
* Finally we increment the previous count by 1.
* We repeat the process for the second string. Iterating through all the characters in the second string.
* if there is no key for it from string 1. Then we know we don't have an anagram.
* Otherwise simply decrement the count
* Finally we go through all the values in the characterCount map
* and simply make sure that every value is 0.
* This ensures that we saw an equal number of character counts in string 1 (during incrementing) and string 2 (during decrementing).

***Select the implementation***
* Since we are simply looping through the characters in the two strings and doing constant amount of work in each iteration the time complexity of this version is of order n (O(n)) where n is the number of characters in the strings.
``````
``````import { areAnagrams } from './anagram';

test('anagrams', () => {
expect(areAnagrams('life', 'file')).toBeTruthy();
expect(areAnagrams('life', 'lifl')).toBeFalsy();
expect(areAnagrams('life', 'lifel')).toBeFalsy();
});
``````
``````/**
* A word is an anagram of another if you can rearrange its characters to produce the second word.
* Given two strings determines if they are anagrams of each other.
* - 'earth' and 'heart' are anagrams
* - 'silent' and 'listen' are anagrams
* - 'foo' and 'bar' are not anagrams
*/
function areAnagrams(s1: string, s2: string): boolean {
const charCount = new Map<string, number>();
for (const char of s1.split('')) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
for (const char of s2.split('')) {
if (!charCount.has(char)) return false;
charCount.set(char, charCount.get(char) - 1);
}
return Array.from(charCount.values()).every(val => val === 0);
}

console.log("listen and silent:")
console.log(areAnagrams("listen", "silent"))

console.log("foo and bar:")
console.log(areAnagrams("foo", "bar"))

``````
``````<!DOCTYPE html>
<html>
<body>
<!-- // make console.log will write to the page for better in-browser experience -->
<script>
(function () {
var body = document.querySelector('body');
body.style['fontFamily'] = 'monospace';
body.style['fontSize'] = '2em';
console.log = function (x) { body.innerText += x + '\n'; };
}());
</script>
<script src="./anagram.js"></script>
</body>
</html>``````