Log inSign up
mediumleetcodeNot Started

Group Anagrams

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation: Anagrams are clustered into three equivalence classes: "aet" -> ["eat","tea","ate"], "ant" -> ["tan","nat"], "abt" -> ["bat"].

Example 2 · Example:

Input: strs = [""]
Output: [[""]]
Explanation: Empty string is an anagram of itself.

Example 3 · Example:

Input: strs = ["a"]
Output: [["a"]]
Explanation: Single character string forms a single group.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Design canonical representation keys for equivalence class partitioning.
  • Compare sorted string keys vs frequency tuple keys.
  • Implement high-performance hash map grouping across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Grouping objects together based on permutation equivalence or invariant properties.
  • When comparing collections of strings where letter order is irrelevant.

Algorithmic Decision Tree:

  • Canonical Form Hashing
  • Equivalence Partitioning with Hash Map

Connected Patterns:

Valid AnagramFind All Anagrams in a StringGroup Shifted Strings

1. Pairwise Anagram Comparison

Intuition

Maintain a boolean visited array. For each unvisited string strs[i], start a new group with strs[i]. Iterate j from i + 1 to n - 1: if strs[j] is unvisited and is an anagram of strs[i], add it to the current group and mark visited[j] = true. Append the group to the final result.

When to apply: Exploratory naive baseline.

Algorithm

  1. Initialize visited = [false] * n and result = [].
  2. Loop i from 0 to n - 1:
  3. If visited[i] is true, continue.
  4. Create group = [strs[i]] and mark visited[i] = true.
  5. Loop j from i + 1 to n - 1:
  6. If !visited[j] and isAnagram(strs[i], strs[j]), add strs[j] to group and mark visited[j] = true.
  7. Add group to result.
  8. Return result.

Pairwise Anagram Comparison

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [eat, tea, tan, ate, nat, bat]
Current operationSTEP 1 OF 6
Observation: Track visited array of size 6
Visual state
Values and pointers at this exact step
array
S
eat
tea
tan
ate
nat
bat
0
↑ WORD 0: 'eat'
1
2
3
4
5
Variables at this step
activeWord
eat
visited
[true,false,false,false,false,false]
groups
[["eat"]]
Check / comparison
Start group 1 with unvisited word 'eat'. Compare pairwise with all remaining words.
Decision / next transition
Initialize Group 1: ['eat'].
Why this step matters

Observation: Track visited array of size 6. First unvisited word is strs[0] = 'eat'.

Decision: Create Group 1 with 'eat'. Now scan all subsequent unvisited words.

Invariant: Words assigned to a group are marked visited to prevent duplicate grouping.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6 bool isAnagram(const std::string& a, const std::string& b) {
7 if (a.size() != b.size()) return false;
8 int count[26] = {0};
9 for (char c : a) count[c - 'a']++;
10 for (char c : b) {
11 if (--count[c - 'a'] < 0) return false;
12 }
13 return true;
14 }
15public:
16 std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
17 int n = strs.size();
18 std::vector<bool> visited(n, false);
19 std::vector<std::vector<std::string>> result;
20
21 for (int i = 0; i < n; ++i) {
22 if (visited[i]) continue;
23 std::vector<std::string> group;
24 group.push_back(strs[i]);
25 visited[i] = true;
26 for (int j = i + 1; j < n; ++j) {
27 if (!visited[j] && isAnagram(strs[i], strs[j])) {
28 group.push_back(strs[j]);
29 visited[j] = true;
30 }
31 }
32 result.push_back(group);
33 }
34 return result;
35 }
36};
37
38int main() {
39 Solution sol;
40 std::vector<std::string> strs = {"eat","tea","tan","ate","nat","bat"};
41 auto ans = sol.groupAnagrams(strs);
42 for (const auto& grp : ans) {
43 std::cout << "[ ";
44 for (const auto& w : grp) std::cout << w << " ";
45 std::cout << "] ";
46 }
47 std::cout << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N^2 * K) — Takes O(N2) pairwise comparisons, each taking O(K) time.
  • Space complexity: O(N * K)

Why Brute Force Doesn't Scale:

Using a 26-tuple / count string bypasses comparison sorting entirely, dropping time from O(N * K log K) to O(N * K).

Reusing a single 26-element buffer for count generation minimizes GC pressure.

2. Sorted String Key Hashing

Intuition

For every string s in strs, sort its characters to produce sortedStr. Use sortedStr as a key in a hash map whose values are lists of strings. Push s to map[sortedStr]. Finally, collect all value lists from the hash map into the result.

When to apply: The standard industry solution when maximum simplicity and readability are paramount.

Algorithm

  1. Initialize a hash map groups = {} mapping string -> list<string>.
  2. For each string s in strs:
  3. Create key = sort(s).
  4. Add s to groups[key].
  5. Collect and return all list values from groups.

Sorted String Key Hashing

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [eat, tea, tan, ate, nat, bat]
Current operationSTEP 1 OF 6
Observation: Initialize hash map
Visual state
Values and pointers at this exact step
array
S
eat
tea
tan
ate
nat
bat
0
↑ SORT 'eat' -> 'aet'
1
2
3
4
5
Variables at this step
map
{"aet":["eat"]}
Check / comparison
Map empty. Sort 'eat' -> 'aet'. Insert map['aet'] = ['eat'].
Decision / next transition
Hash map associates canonical sorted signature with list of words.
Why this step matters

Observation: Initialize hash map. Sort first word strs[0] = 'eat' -> 'aet'.

Decision: Insert into map: {'aet': ['eat']}.

Invariant: All mutual anagrams generate identical sorted string keys.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5#include <algorithm>
6
7class Solution {
8public:
9 std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
10 std::unordered_map<std::string, std::vector<std::string>> mp;
11 for (const std::string& s : strs) {
12 std::string key = s;
13 std::sort(key.begin(), key.end());
14 mp[key].push_back(s);
15 }
16 std::vector<std::vector<std::string>> result;
17 result.reserve(mp.size());
18 for (auto& [key, group] : mp) {
19 result.push_back(std::move(group));
20 }
21 return result;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::vector<std::string> strs = {"eat","tea","tan","ate","nat","bat"};
28 auto ans = sol.groupAnagrams(strs);
29 for (const auto& grp : ans) {
30 std::cout << "[ ";
31 for (const auto& w : grp) std::cout << w << " ";
32 std::cout << "] ";
33 }
34 std::cout << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N * K log K) — Sorting each of the N strings of max length K takes O(K log K). Hash map operations are O(K).
  • Space complexity: O(N * K)

3. 26-Character Frequency Signature Hashing (O(N * K))

Intuition

For each string, compute a 26-element integer frequency array. Convert this array into a unique hashable string key (e.g. #1#0#0#...#1 or tuple). Store the string into the hash map under this frequency key. This completely bypasses comparison sorting.

When to apply: When strings are very long (K is large) and sorting adds measurable overhead.

Algorithm

  1. Initialize hash map map.
  2. For each string s in strs:
  3. Count character frequencies in int count[26] = {0}.
  4. Construct delimiter key key encoding all 26 counts.
  5. Add s to map[key].
  6. Return all list values from map.

Canonical 26-Tuple Hash Group Partitioning

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [eat, tea, tan, ate, nat, bat]
Current operationSTEP 1 OF 6
Observation: Inspect strs[0] = "eat"
Visual state
Values and pointers at this exact step
array
S
eat
tea
tan
ate
nat
bat
0
↑ strs[0] = "eat"
1
2
3
4
5
Variables at this step
word
eat
canonicalKey
a1e1t1
groups
{"a1e1t1":["eat"]}
Why this step matters

Observation: Inspect strs[0] = "eat". Count character frequencies: { a: 1, e: 1, t: 1 }.

Decision: Generate signature key "a1e1t1" and add "eat" to its list.

Invariant: All anagrams produce the identical canonical frequency signature.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
9 std::unordered_map<std::string, std::vector<std::string>> mp;
10 for (const std::string& s : strs) {
11 int count[26] = {0};
12 for (char c : s) count[c - 'a']++;
13
14 std::string key = "";
15 for (int i = 0; i < 26; ++i) {
16 key += "#" + std::to_string(count[i]);
17 }
18 mp[key].push_back(s);
19 }
20
21 std::vector<std::vector<std::string>> result;
22 result.reserve(mp.size());
23 for (auto& [key, group] : mp) {
24 result.push_back(std::move(group));
25 }
26 return result;
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::string> strs = {"eat","tea","tan","ate","nat","bat"};
33 auto ans = sol.groupAnagrams(strs);
34 for (const auto& grp : ans) {
35 std::cout << "[ ";
36 for (const auto& w : grp) std::cout << w << " ";
37 std::cout << "] ";
38 }
39 std::cout << std::endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N * K) — Counting characters for each string of length K takes O(K), and key construction takes O(26) = O(1). Total time is O(N * K).
  • Space complexity: O(N * K)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Pairwise Comparison Brute ForceO(N^2 * K)O(N * K)No hash map needed.Quadratic time complexity, will TLE for N = 10,000.
2.Sorted String as Hash Map KeyO(N * K log K)O(N * K)Cleanest, most readable code, highly standard across all languages.Slight O(log K) factor overhead per word.
3.26-Character Frequency Signature KeyOptimalO(N * K)O(N * K)Strictly linear O(N * K) time complexity, optimal when K is large.Key formatting string overhead.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not including a delimiter when stringifying frequency counts (e.g. count 1,11 vs 11,1).

Pitfall 2:

Using nested loops resulting in O(N2 * K) timeout.

Crucial Edge Cases to Validate:

  • strs contains empty string strs = [""]: Empty string generates key "" or all zeros vector, mapped to [[""]].
  • Single string strs = ["a"]: Generates single entry map and returns [["a"]].
  • All strings are identical or anagrams of each other: All strings mapped under single key, returns 1 group containing all N strings.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both sorted-key and frequency-tuple methods to show full breadth of understanding.
  2. Highlight the delimiter collision pitfall when formatting frequency keys.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is a delimiter like # needed when joining 26 integer counts into a string key?

Back to DSA Sheet