49. Group Anagrams

Intuition

Anagrams are words that contain the same characters with the same frequencies, just in a different order. To group anagrams, we need a way to recognize that two different strings are actually composed of the same characters. Sorting is one way, but it’s inefficient for large inputs. A more optimal method is to use a character count array as a signature or key for grouping words.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N.K)$

Code

public List<List<String>> groupAnagrams(String[] inputWords) {
    // Map to hold the signature key and list of anagrams
    Map<String, List<String>> anagramGroups = new HashMap<>();

    // Iterate through each word in the input array
    for (int i = 0; i < inputWords.length; ++i) {
        String currentWord = inputWords[i];
        
        // Character frequency array for 26 lowercase letters
        int[] charFrequency = new int[26];
        
        // Build the frequency map for the current word
        for (int j = 0; j < currentWord.length(); ++j) {
            charFrequency[currentWord.charAt(j) - 'a']++;
        }

        // Convert frequency array to a unique string key
        String frequencyKey = Arrays.toString(charFrequency);

        // If key doesn't exist, initialize a new list
        if (!anagramGroups.containsKey(frequencyKey)) {
            anagramGroups.put(frequencyKey, new ArrayList<>());
        }

        // Add the current word to its anagram group
        anagramGroups.get(frequencyKey).add(currentWord);
    }

    // Return all grouped anagrams
    return new ArrayList<>(anagramGroups.values());
}