Group Anagrams

In this article, we’ll explore different approaches to solving this problem, from brute force solution to a more optimized solution. So sit back, relax, and let’s get ready to group those anagrams like a pro!

Problem Statement:

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Well, well, well, doesn’t the problem statement looks deceptively easy? You might be thinking to yourself, “Pfft, I’ve already tackled the Leetcode 242 — Valid Anagram. How hard can this be?” But hold onto your hats, folks, because this question is a whole other ballgame. It requires some serious critical thinking and problem-solving skills. So without further ado, let’s get started with the solution.

Approach 1: Brute Force

1. Here we compare every pair of strings to check if they are anagrams.

2. For each string in the input array, Iterate the entire input array and compare the strings to check if they are anagrams, or not.

3. If they are anagrams, add them to the same group.

4. Note: a helper function can be used to validate if two strings are anagrams or not.

// ES6 Arrow Function
const groupAnagrams = strs => {
    // Helper function
    const validAnagram = (s1, s2) => {
        return s1.split('').sort().join('') === s2.split('').sort().join('');
    }

    const allGroups = [];

    for(let i = 0; i < strs.length; i++) {
        const group = [strs[i]];
        for(let j = i+1; j < strs.length; j++) {
            if(validAnagram(strs[i], strs[j])) {
                group.push(strs[j]);
            }
        }

        allGroups.push(group);
    }

    return allGroups;
}

Time Complexity: O(N² * KLogK)

Space Complexity: O(N²)

Note 1: It is highly inefficient and should be avoided for large inputs.

Note 2: The above method has a minor limitation in that it may return duplicate values in the result. However, we can easily modify the code to avoid this and ensure that only unique values are returned.

Approach 1.1:

1. we keep track of the visited strings using a boolean array called visited.

2. Before starting a new group, we check if the current string has already been visited. If it has, we skip it and move on to the next string.

3. Similarly, while comparing with other strings, we skip visited strings to avoid duplicates.

// ES6 Arrow Function
const groupAnagrams = strs => {
    // Helper function 
    const isAnagram = function(s1, s2) {
        return s1.split('').sort().join('') === s2.split('').sort().join('');
    }

    const allGroups = [];
    // To keep track of visited strings
    const visited = new Array(strs.length).fill(false); 

    for (let i = 0; i < strs.length; i++) {
        if (visited[i]) continue; // Skip visited strings

        const group = [strs[i]];
        visited[i] = true;

        for (let j = i + 1; j < strs.length; j++) {
            if (visited[j]) continue; // Skip visited strings

            if (isAnagram(strs[i], strs[j])) {
                group.push(strs[j]);
                visited[j] = true;
            }
        }

        allGroups.push(group);
    }

    return allGroups;
};

Time Complexity: O(N² * K LogK)

Space Complexity: O(N)

Note: This is highly inefficient and should be avoided for large inputs.

Approach 2: Maps and Sorting

1. So the Idea is to sort each string in the list and store it in a hashmap.

2. The sorted string is used as the key, and the original string is added to the list of values corresponding to that key.

3. This way, anagrams will be grouped together under the same key.

// ES6 Arrow Function
const groupAnagrams = strs => {
    let map = new Map();

    for(let i of strs) {
        let sorted = i.split('').sort().join('');
        if(map.has(sorted)) {
            map.get(sorted).push(i);
        } else {
            map.set(sorted, [i]);
        }
    }

    return Array.from(map.values());
}

Time Complexity: O(N K log(K))

Space Complexity: O(N * K)

Note: N is the number of strings and K is the maximum length of a string.

Approach 3: Character Count

Instead of sorting each string, we can use a hashmap to count the occurrence of each character in the string. The character counts can then be used as a key to group anagrams.

1. Create an empty Map to store the groups of anagrams.

2. Loop through each string in the input array.

3. Create a count array to store the number of occurrences of each character in the current string.

4. Use the count array as a key in the Map, and add the current string to the array of anagrams corresponding to this key. If the key doesn’t exist in the Map, create a new key-value pair.

5. After looping through all the strings, return the array of anagram groups.

// ES6 Arrow Function
const groupAnagrams = strs => {
    let map = new Map();

    for(let str of strs) {
        let count = new Array(26).fill(0);
        for(let i = 0; i < str.length; i++) {
            const charIdx = str.charCodeAt(i) - 97;
            count[charIdx]++;
        }

        const key = count.join('#');

        if(map.has(key)) {
            map.get(key).push(str);
        } else {
            map.set(key, [str]);
        }
    }

    return Array.from(map.values());
}

Time Complexity: O(N * K)

Space Complexity: O(N * K)

Note: If you will notice the key variable, which is used to store the count.join('#') value. You will notice that we are using a separator to join the array into a string. Why?

The reason we’re using a separator to join the array into a string is that we need a unique identifier for each count array. For example, let’s say we have two words “ate” and “eat”. When we count the characters in each word, we get the arrays[1, 0, 0, 0, 1, 0,.., 0, 0, 0, 0, 1,..., 0, 0, 0] and [1, 0, 0, 0, 1, 0,.., 0, 0, 0, 0, 1,..., 0, 0, 0].

We can’t directly use these arrays as keys in a map or object to group the anagrams because arrays are objects in JS and their equality is determined by reference, not by value. So if we use these arrays as keys, we won’t be able to group the anagrams correctly.

To overcome this, we use a separator to join the count array into a string. For example, if we use “#” as the separator, the count arrays for “ate” and “eat” would become the strings 1#0#0#1#0#0#0#0#0#…#0 and 1#0#0#1#0#0#0#0#0#…#0 respectively.

Now we can use these strings as keys in a map or object to group the anagrams because strings are compared by value, not by reference.

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 49