The Anagram Game

The rules of the game

A word is an anagram of another if you can rearrange its characters to produce the second word. We are going to write a function in typescript that takes two strings as arguments and returns a boolean indicating if they are indeed anagrams of one another.

Naive implementation

Let's start by defining the function

function isAnagram(s1: string, s2: string): boolean {
    // implementation here
}

We have two inputs, named s1 and s2 both with the string type. The function will return a boolean as indicated by the return type annotation. So far so good. Let's try something...

function isAnagram(s1: string, s2: string): boolean {
    s1 = s1.split('').sort().join('');
    s2 = s2.split('').sort().join('');
    return s1 === s2;
}

For each string:

1. Split the string into individual characters to produce a string array.
2. Sort the characters using the Arrays built-in sort method.
3. Join the arrays to produce a single, now sorted, string value.

The final return statement does a comparison between the two strings and returns true if they match and false if they do not. As the strings are now both sorted alphabetically this will give us the desired result.

We can do better!

This is an adequate implementation for small strings, but because of the use of sort, it can have performance implications with larger strings. Implementations of the sort function vary from browser to browser as the specification does not dictate how to implement the sort function itself. Let's take Chrome's V8 Javascript engine as an example. From shovonhasan.com...

For arrays containing 10 or fewer elements, time complexity of .sort is O(n^2), and space complexity is O(1). For longer arrays time complexity is O(n log(n)) (average case), and space complexity is O(log(n))

Big O notation is a way of reasoning about the performance implications of an algorithm. In this case, the bigger the input array the longer it will take to execute to a scale of n log(n).

So let's try something a little different.

function isAnagram(s1: string, s2: string): boolean {

    const counts = s1.split("").reduce<{[char: string]: number}>((output, char) => {
        counts[char] = (counts[char] || 0) + 1;
        return output;
    }, {});

    const split2 = s2.split("");
    for (let i = 0; i < split2.length; i++) {
        if (!counts[s2[i]]) return false;
        counts[s2[i]]--;
    }

    const values = Object.values(counts);
    return values.every(v => v === 0);

}

We go through the following steps:

1. We split the first string into an array of characters.
2. For each character in the array we keep a count of the number of occurrences.
3. We split the second string into an array of characters.
4. For each character in the array we first check to see if it was seen in the first string. If it was, we decrement the count for that letter. If not, we can shortcut the rest of the loop and the remaining function and return false.
5. Finally we loop through all the counts and return true if all the values are 0 (i.e. we had the same letters in each string) or false if not.

The advantage of this implementation is that the complexity is reduced to O(n) where n is the number of characters. This will therefore scale with greater efficiency than the previous version. We can also bail on the loop and remaining function at the earliest point at which we know they are not a match.

Conclusion

There is always more than one way to crack an egg. Big O notation gives us a tool to think through the performance implications of our algorithms and helps us make informed decisions based on this. It is important to note however the old mantra - "Don't optimise too soon" or more accurately - "Don't optimise until you know what to optimise".