Group Anagrams - LeetCode Daily Challenge

Problem Statement

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2

Input: strs = ["a"]
Output: [["a"]]

Try here before watching the video.

Video Solution

Approach 1 - Categorize by Sorted String

Java Code

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) { 
        HashMap<String, List<String>> anagrams = new HashMap<>();
        
        for(String s : strs) {
            char c[] = s.toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            if(!anagrams.containsKey(key)) {
                anagrams.put(key, new ArrayList<>());
            }
            anagrams.get(key).add(s);
        
        }
        return new ArrayList(anagrams.values());
    }
}

C++ Code

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagrams;
        for (const auto& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            anagrams[key].push_back(s);
        }
        vector<vector<string>> result;
        for (const auto& entry : anagrams) {
            result.push_back(entry.second);
        }
        return result;
    }
};

Python Code

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}
        for s in strs:
            key = ''.join(sorted(s))
            if key not in anagrams:
                anagrams[key] = []
            anagrams[key].append(s)
        return list(anagrams.values())

Javascript Code

var groupAnagrams = function(strs) {
    const anagrams = new Map();
    for (const s of strs) {
        const key = [...s].sort().join('');
        if (!anagrams.has(key)) {
            anagrams.set(key, []);
        }
        anagrams.get(key).push(s);
    }
    return Array.from(anagrams.values());
};

Go Code

func groupAnagrams(strs []string) [][]string {
	anagrams := make(map[string][]string)
	for _, s := range strs {
		key := sortString(s)
		anagrams[key] = append(anagrams[key], s)
	}

	result := make([][]string, 0, len(anagrams))
	for _, group := range anagrams {
		result = append(result, group)
	}

	return result
}

func sortString(s string) string {
	str := []byte(s)
	sort.Slice(str, func(i, j int) bool {
		return str[i] < str[j]
	})
	return string(str)
}

Complexity Analysis

• Time Complexity: O(N * K log⁡K), where N is the length of strs, and K is the maximum length of a string in strs. The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(Klog⁡K) time.
• Space Complexity: O(N * K), the total information content stored in anagrams.

Approach 2 - Categorize by Count

Java Code

class Solution {
    
    private String generateKey(String str) {
        int[] count = new int[26];
        for (char ch : str.toCharArray()) {
            count[ch - 'a'] += 1;
        }
        
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < 26; i++) {
            sb.append('#');
            sb.append(count[i]);
        }
        return sb.toString();
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> anagrams = new HashMap<>();
        
        for(int i = 0; i < strs.length; i++) {
            String key = generateKey(strs[i]);
            if(!anagrams.containsKey(key)) {
                anagrams.put(key, new ArrayList<>());
            }
            anagrams.get(key).add(strs[i]);
        }
        
        return new ArrayList<>(anagrams.values());
    }
}

C++ Code

class Solution {
private:
    string generateKey(const string& str) {
        vector<int> count(26, 0);
        for (char ch : str) {
            count[ch - 'a'] += 1;
        }

        string key = "";
        for (int i = 0; i < 26; i++) {
            key += '#';
            key += to_string(count[i]);
        }
        return key;
    }

public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagrams;

        for (const string& s : strs) {
            string key = generateKey(s);
            if (anagrams.find(key) == anagrams.end()) {
                anagrams[key] = vector<string>();
            }
            anagrams[key].push_back(s);
        }

        vector<vector<string>> result;
        for (const auto& entry : anagrams) {
            result.push_back(entry.second);
        }
        return result;
    }
};

Python Code

class Solution:
    def generateKey(self, s: str) -> str:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        
        key = '#'.join(['#'.join(map(str, count))])
        return key

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        
        for s in strs:
            key = self.generateKey(s)
            anagrams[key].append(s)
        
        return list(anagrams.values())

Javascript Code

var groupAnagrams = function(strs) {
    
    const generateKey = (str) => {
        const count = Array(26).fill(0);
        for (const ch of str) {
            count[ch.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
        }
        return count.map(num => `#${num}`).join('');
    };

    const anagrams = new Map();
    for (const s of strs) {
        const key = generateKey(s);
        if (!anagrams.has(key)) {
            anagrams.set(key, []);
        }
        anagrams.get(key).push(s);
    }
    return Array.from(anagrams.values());
};

Go Code

func generateKey(s string) string {
	count := make([]int, 26)
	for _, ch := range s {
		count[ch-'a'] += 1
	}

	var builder strings.Builder
	builder.WriteByte('#')
	for _, num := range count {
		builder.WriteString(fmt.Sprintf("#%d", num))
	}
	return builder.String()
}

func groupAnagrams(strs []string) [][]string {
	anagrams := make(map[string][]string)

	for _, s := range strs {
		key := generateKey(s)
		anagrams[key] = append(anagrams[key], s)
	}

	result := make([][]string, 0, len(anagrams))
	for _, group := range anagrams {
		result = append(result, group)
	}

	return result
}

Complexity Analysis

• Time Complexity: O(N * K), where N is the length of strs, and K is the maximum length of a string in strs. Counting each string is linear in the size of the string, and we count every string.
• Space Complexity: O(N * K), the total information content stored in anagrams.