Problem 15 - Group Anagrams

Explore our archive for previous posts.

Question

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 = [""]
Output: [[""]]

Example 3:

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

Constraints:

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] consists of lowercase English letters.

Approach

The solution uses a counting sort-based approach to group anagrams together. It iterates through each string in the input array and generates a unique key for each string based on the frequency of characters. Strings with the same key are grouped together using a HashMap. This is because two strings are anagrams when they have the same set of characters the same number of times, just their relative order being different. As such, if two strings are anagrams of each other, generating a key based on the frequencies of individual characters should result in the same value. Finally, the values of the HashMap are converted to an ArrayList to obtain the grouped anagrams.

Solution

Solve it here

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            String key = generateKey(str);
            
            // Check if the key exists in the map.
            // If not, create a new ArrayList and associate it with the key.
            // If yes, retrieve the existing ArrayList associated with the key.
            // In both cases, add the current string to the ArrayList.
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }

        // Convert the values of the map to an ArrayList and return.
        return new ArrayList<>(map.values());
    }

    private String generateKey(String str) {
        int[] count = new int[26]; // Assuming input contains only lowercase letters
        
        // Count the frequency of each character in the string.
        for (char c : str.toCharArray()) {
            count[c - 'a']++;
        }

        // Build the key by concatenating the counts with a delimiter (#).
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            sb.append('#').append(count[i]);
        }
        return sb.toString();
    }
}

Time and space complexity

Time Complexity: Iterating through each string in the input array takes O(N), where N is the number of strings. Counting the frequency of characters in each string takes O(K), where K is the maximum length of a string. Constructing the key for each string takes O(K). The overall time complexity is O(N * K) since we perform these operations for each string.

Space Complexity: We use a HashMap to store the grouped anagrams, which requires O(N * K) space in the worst case. The count array for each string requires O(K) space. The overall space complexity is O(N * K).