Group Anagrams

59.1k
0

Given an array strs containing N strings made of lowercase English letters, place all anagrams inside the same group.

Anagrams contain identical character frequencies, although character order may differ. Return all groups in any order.

Example 1

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

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

Explanation:

  • "eat", "tea", and "ate" contain one 'a', one 'e', and one 't'.

  • "tan" and "nat" contain one 'a', one 'n', and one 't'.

  • "bat" has no other anagram inside the input.

Group order can differ without affecting correctness.

Example 2

Input: strs = [""]

Output: [[""]]

Explanation:

The empty string forms a valid group containing one string.

Example 3

Input: strs = ["a"]

Output: [["a"]]

Explanation:

A single string forms one anagram group.

Brute Force Approach

Every processed word must either join an existing anagram group or begin a new group. Without a reusable identifier for each group, group selection requires comparison against already created groups.

The first word of every group can serve as a representative because all members of one group share the same characters and frequencies. Sorting the candidate word and the representative produces comparable forms. Equal sorted forms identify a matching group, while unequal forms require another group comparison.

Algorithm

  • Initialize an empty 2D list groups to store all anagram groups.

  • Traverse every string word in strs.

  • Initialize a Boolean variable placed with false to track successful insertion into an existing group.

  • Traverse every existing group and select the first string as the group representative.

  • Check the candidate and representative lengths before sorting, because strings with different lengths cannot be anagrams.

  • Sort separate copies of both strings and compare the sorted forms.

  • Append word to the current group and set placed to true after equal sorted forms appear.

  • Stop further group comparisons after successful insertion, because one word belongs to exactly one anagram group.

  • Create a new group containing only word when placed remains false.

  • Return groups after processing every input string.

Dry Run

k

k

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Checks whether two strings are anagrams. */
bool isAnagram(
const string& first,
const string& second
) {
// Different lengths cannot form anagrams.
if (first.length() != second.length()) {
return false;
}
// Sort separate copies for direct comparison.
string sortedFirst = first;
string sortedSecond = second;
sort(
sortedFirst.begin(),
sortedFirst.end()
);
sort(
sortedSecond.begin(),
sortedSecond.end()
);
return sortedFirst == sortedSecond;
}
public:
/* Groups anagrams through pairwise group checks. */
vector<vector<string>> groupAnagrams(
vector<string>& strs
) {
vector<vector<string>> groups;
// Place every word into a matching group.
for (const string& word : strs) {
bool placed = false;
// Compare against one representative per group.
for (vector<string>& group : groups) {
if (isAnagram(word, group[0])) {
group.push_back(word);
placed = true;
break;
}
}
// Start a new group after no match.
if (!placed) {
groups.push_back({word});
}
}
return groups;
}
};
// Driver code to execute the solution.
int main() {
vector<string> strs = {
"eat",
"tea",
"tan",
"ate",
"nat",
"bat"
};
Solution solution;
vector<vector<string>> answer =
solution.groupAnagrams(strs);
// Print every generated group.
for (const vector<string>& group : answer) {
cout << "[";
for (
int i = 0;
i < (int)group.size();
i++
) {
cout << '"'
<< group[i]
<< '"';
if (i + 1 < (int)group.size()) {
cout << ", ";
}
}
cout << "]" << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N² × K log K) in the worst case, where N represents the number of strings and K represents the maximum string length. A word can be compared with O(N) existing groups, and every comparison can sort two strings in O(K log K) time.

Space Complexity: O(N × K) including the returned groups. Excluding output storage, O(K) temporary space is required for sorted copies during one anagram comparison.

Better Approach

The Brute Force Approach repeatedly searches existing groups and repeatedly sorts group representatives. A large number of groups can therefore cause nearly every new word to be compared with many earlier representatives.

Anagrams always produce the same sorted character sequence. A Hash Map can associate each sorted sequence with all original words sharing the sequence. One sorted key per input word removes pairwise group searches and places every word directly inside the correct group.

Algorithm

  • Initialize an empty Hash Map groupedWords.

  • Traverse every string word in strs.

  • Create a copy of word to preserve the original string.

  • Sort the copied characters to form a canonical key.

  • Create an empty list for the key when no matching map entry exists.

  • Append the original word to the list associated with the sorted key.

  • Extract every list stored inside the Hash Map after complete traversal.

  • Return the extracted lists as the final grouping.

Dry Run

k

k

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Groups anagrams with sorted-string keys. */
vector<vector<string>> groupAnagrams(
vector<string>& strs
) {
unordered_map<
string,
vector<string>
> groupedWords;
// Build one sorted key for every word.
for (const string& word : strs) {
string key = word;
sort(
key.begin(),
key.end()
);
// Store the original word under the key.
groupedWords[key].push_back(word);
}
vector<vector<string>> groups;
// Extract all groups from the Hash Map.
for (const auto& entry : groupedWords) {
groups.push_back(entry.second);
}
return groups;
}
};
// Driver code to execute the solution.
int main() {
vector<string> strs = {
"eat",
"tea",
"tan",
"ate",
"nat",
"bat"
};
Solution solution;
vector<vector<string>> answer =
solution.groupAnagrams(strs);
// Print every generated group.
for (const vector<string>& group : answer) {
cout << "[";
for (
int i = 0;
i < (int)group.size();
i++
) {
cout << '"'
<< group[i]
<< '"';
if (i + 1 < (int)group.size()) {
cout << ", ";
}
}
cout << "]" << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N × K log K) on average, where N represents the number of strings and K represents the maximum string length. Every string is sorted once, and each Hash Map operation requires average O(1) access after key processing.

Space Complexity: O(N × K), because the Hash Map stores sorted keys and all grouped strings. The returned groups also contain up to N × K characters.

Optimal Approach

The Better Approach removes pairwise group comparisons, but sorting every string still requires O(K log K) time for a string containing K characters. Full character order is unnecessary because anagram detection only depends on the frequency of each letter.

A fixed lowercase English alphabet contains only 26 possible characters. A 26-position frequency signature can therefore represent every string. Equal signatures identify anagrams without sorting, reducing character processing to one linear traversal per string.

A serialized key requires separators between adjacent counts. Separators prevent different frequency sequences, such as counts 1, 10 and 11, 0, from producing the same key.

Algorithm

  • Initialize an empty Hash Map groupedWords.

  • Traverse every string word in strs.

  • Initialize a frequency array of size 26 with zero values.

  • Traverse every character in word.

  • Convert each character into an index from 0 to 25 using the distance from 'a'.

  • Increment the frequency stored at the calculated index.

  • Convert all 26 frequencies into a stable key.

  • Insert a delimiter between adjacent counts to prevent ambiguous multi-digit combinations.

  • Create an empty group for a previously unseen frequency key.

  • Append the original word to the group associated with the frequency key.

  • Extract all map values after processing every word.

  • Return the extracted groups.

Dry Run

p

p

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Builds a key from lowercase character counts. */
string buildKey(const string& word) {
array<int, 26> frequency{};
// Count every lowercase English letter.
for (char character : word) {
frequency[character - 'a']++;
}
string key;
// Separate counts to avoid ambiguous keys.
for (int count : frequency) {
key.push_back('#');
key += to_string(count);
}
return key;
}
public:
/* Groups anagrams with frequency keys. */
vector<vector<string>> groupAnagrams(
vector<string>& strs
) {
unordered_map<
string,
vector<string>
> groupedWords;
// Build one frequency key for every word.
for (const string& word : strs) {
string key = buildKey(word);
// Store the original word under the key.
groupedWords[key].push_back(word);
}
vector<vector<string>> groups;
// Extract all groups from the Hash Map.
for (const auto& entry : groupedWords) {
groups.push_back(entry.second);
}
return groups;
}
};
// Driver code to execute the solution.
int main() {
vector<string> strs = {
"eat",
"tea",
"tan",
"ate",
"nat",
"bat"
};
Solution solution;
vector<vector<string>> answer =
solution.groupAnagrams(strs);
// Print every generated group.
for (const vector<string>& group : answer) {
cout << "[";
for (
int i = 0;
i < (int)group.size();
i++
) {
cout << '"'
<< group[i]
<< '"';
if (i + 1 < (int)group.size()) {
cout << ", ";
}
}
cout << "]" << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N × K) on average, where N represents the number of strings and K represents the maximum string length. Every character is counted once, and building the fixed 26-position key requires constant alphabet work per string.

Space Complexity: O(N × K) including the returned groups. The Hash Map additionally stores one fixed-alphabet signature per distinct anagram group.

FAQs about Group Anagrams

1. Why does sorting produce a valid anagram key?

Anagrams contain identical characters with identical frequencies. Sorting places equal characters in the same order, so all anagrams produce the same sorted string.

2. Why is comparison with only the first string of a group sufficient?

Every member of a valid group is an anagram of the group representative. A candidate matching the representative therefore belongs to the same group.

3. Why are separators required inside a frequency key?

Simple count concatenation can create ambiguous keys. Counts 1 and 10 produce "110", while counts 11 and 0 also produce "110".

Delimited forms remain different:

1#10

11#0

4. How is an empty string handled?

An empty string produces a frequency signature containing 26 zero counts. Every empty string therefore belongs to the same group.

5. Can the output order differ?

Yes. Hash Maps generally do not preserve a required traversal order. Any group order remains valid unless a separate ordering requirement is added.

6. Does the Frequency Array Approach support uppercase letters or Unicode characters?

The 26-position implementation supports lowercase English letters only. Mixed character sets require a larger fixed array, a character-frequency map, or the Sorting Approach.

7. Does Hash Map access always require O(1) time?

Hash Map insertion and lookup require O(1) average time. Severe hash collisions can produce slower worst-case behaviour.

8. Does the Sorting Approach modify the original strings?

No. Every implementation creates a separate sorted copy for the key. Original strings remain unchanged inside the returned groups.

ArraysStringHashingSorting

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0] , mat[1][1] , and mat[2][2] . Input: mat = [[10, 20, 30], [40, 50, 60]] Output: 10 50 Exp...

67.1k
Comments0