49. Group Anagrams - Solution & Explanation

The problem

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

Example 1:

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

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

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

1 <= strs.length <= 10⁴
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Approach overview

Problem Overview: You receive an array of strings and must group words that are anagrams of each other. Two strings belong in the same group if they contain the same characters with the same frequency, regardless of order.

Approach 1: Hash Map + Character Frequency (O(n * k))

This method builds a frequency signature for every string. For each word, count how many times each letter appears using a fixed-size array of length 26. Convert that frequency array into a hashable key (for example a tuple or string) and store the word in a hash map where the key represents the character distribution. Words with identical frequency signatures are anagrams and end up in the same bucket.

The key insight: anagrams share identical character counts. Instead of sorting characters, you directly encode the frequency of each letter. Each string requires a single pass to build its signature, giving O(n * k) time where n is the number of strings and k is the average string length. Space complexity is O(n * k) due to storing grouped strings in the map. This approach heavily relies on a hash table for constant-time grouping.

Approach 2: Sorting Characters as Key (O(n * k log k))

A simpler and very common solution sorts each string alphabetically and uses the sorted string as the key in a hash map. For example, "eat", "tea", and "ate" all become "aet" after sorting. When you iterate through the input, sort the characters of each word, then append the original word to the list stored under that sorted key.

This approach is easy to implement and works well for interview settings. Sorting each word takes O(k log k), so the total runtime becomes O(n * k log k). Space complexity remains O(n * k) for storing groups and keys. It combines string manipulation with sorting and hash-based grouping.

Recommended for interviews: The sorting-based hash map approach is the most widely expected solution because it is concise and easy to reason about. Many candidates start there. The frequency-count approach is more optimal asymptotically since it avoids sorting and runs in O(n * k). Showing both approaches demonstrates solid understanding of hashing, string manipulation, and algorithmic tradeoffs.

Approach 1: Approach 1: Dynamic Programming

This approach involves using dynamic programming to store solutions to subproblems in a table and build up to the solution of the original problem. By doing so, we can avoid redundant calculations and achieve a more efficient solution.

The Python implementation uses a list to keep track of results calculated through the dynamic programming paradigm, spacing out into solving for the entire problem.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Try this approach in the editor

Approach 2: Hash Table

Traverse the string array, sort each string in character dictionary order to get a new string.
Use the new string as key and [str] as value, and store them in the hash table (HashMap<String, List<String>>).
When encountering the same key during subsequent traversal, add it to the corresponding value.

Take strs = ["eat", "tea", "tan", "ate", "nat", "bat"] as an example. At the end of the traversal, the state of the hash table is:

key	value
`"aet"`	`["eat", "tea", "ate"]`
`"ant"`	`["tan", "nat"]`
`"abt"`	`["bat"]`

Finally, return the value list of the hash table.

The time complexity is O(ntimes ktimes log k), where n and k are the lengths of the string array and the maximum length of the string, respectively.

TypeScript

function groupAnagrams(strs: string[]): string[][] {
    const d: Map<string, string[]> = new Map();
    for (const s of strs) {
        const k = s.split('').sort().join('');
        if (!d.has(k)) {
            d.set(k, []);
        }
        d.get(k)!.push(s);
    }
    return Array.from(d.values());
}

func groupAnagrams(strs []string) (ans [][]string) {
	d := map[string][]string{}
	for _, s := range strs {
		t := []byte(s)
		sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
		k := string(t)
		d[k] = append(d[k], s)
	}
	for _, v := range d {
		ans = append(ans, v)
	}
	return
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut map = HashMap::new();
        for s in strs {
            let key = {
                let mut arr = s.chars().collect::<Vec<char>>();
                arr.sort();
                arr.iter().collect::<String>()
            };
            let val = map.entry(key).or_insert(vec![]);
            val.push(s);
        }
        map.into_iter().map(|(_, v)| v).collect()
    }
}

Try this approach in the editor

Approach 3: Counting

We can also change the sorting part in Solution 1 to counting, that is, use the characters in each string s and their occurrence times as key, and use the string s as value to store in the hash table.

The time complexity is O(ntimes (k + C)), where n and k are the lengths of the string array and the maximum length of the string, respectively, and C is the size of the character set. In this problem, C = 26.

TypeScript

function groupAnagrams(strs: string[]): string[][] {
    const map = new Map<string, string[]>();
    for (const str of strs) {
        const k = str.split('').sort().join('');
        map.set(k, (map.get(k) ?? []).concat([str]));
    }
    return [...map.values()];
}

func groupAnagrams(strs []string) (ans [][]string) {
	d := map[[26]int][]string{}
	for _, s := range strs {
		cnt := [26]int{}
		for _, c := range s {
			cnt[c-'a']++
		}
		d[cnt] = append(d[cnt], s)
	}
	for _, v := range d {
		ans = append(ans, v)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Dynamic Programming	Time Complexity: O(n) Space Complexity: O(n)
Hash Table	–
Counting	–

Approach

Complexity

Approach 1: Dynamic Programming

Time Complexity: O(n)

Space Complexity: O(n)

Hash Table

–

Counting

–

Complexity analysis

Approach	Time	Space	When to Use
Hash Map + Character Frequency	O(n * k)	O(n * k)	When optimizing runtime and alphabet size is fixed (e.g., lowercase letters)
Hash Map + Sorted String Key	O(n * k log k)	O(n * k)	General interview solution; simplest and most commonly implemented

Frequently asked questions

Is Group Anagrams easy or hard?

Group Anagrams is generally considered a medium-level problem. The challenge comes from recognizing that anagrams share a canonical representation and using hashing to group them efficiently instead of comparing every pair of strings.

How to solve Group Anagrams in O(n)?

Strict O(n) is not possible because you must inspect each character of every string. However, using a character frequency signature avoids sorting and achieves O(n * k) time, where k is the average string length. Each string is processed once to build a 26-character frequency array used as the hash key.

What is the best approach for Group Anagrams?

The most common approach uses a hash map where the key is the sorted version of each string. After sorting characters in a word, all anagrams produce the same key and are grouped together. This runs in O(n * k log k) time where n is the number of strings and k is the average string length.

What data structure is used in Group Anagrams?

The core data structure is a hash map (dictionary). The key represents the canonical form of the string, such as a sorted string or character frequency signature, and the value stores a list of words that match that key.

What is the time complexity of Group Anagrams?

The typical sorting-based solution runs in O(n * k log k) time because each string must be sorted before grouping. A more optimized approach counts character frequencies and builds a signature key, reducing complexity to O(n * k). Both approaches use O(n * k) space to store grouped strings.

Group Anagrams Python or Java solution approach?

In Python or Java, iterate through the array of strings, compute a key for each string (usually by sorting characters), and store the word in a HashMap or dictionary under that key. After processing all words, return the values of the map as grouped anagrams.

Is Group Anagrams asked at Google, Amazon, or Meta?

Group Anagrams is a common hashing and string manipulation problem frequently asked in coding interviews at companies like Amazon, Google, Meta, and Microsoft. Interviewers use it to evaluate understanding of hash maps, string processing, and algorithmic optimization.

Group Anagrams solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming

Approach 2: Hash Table

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Group Anagrams solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming

Approach 2: Hash Table

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems