Log inSign up
mediumgeeksforgeeksNot Started

Print Anagrams Together

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

Strings
Solve on geeksforgeeks
Lesson

Problem Statement

Given an array of strings string_list of size N, write a program to group all anagrams together and return a list of lists of strings.

Example 1 · Example:

Input: string_list = ["act", "god", "cat", "dog", "tac"]
Output: [["act", "cat", "tac"], ["god", "dog"]]
Explanation: ["act", "cat", "tac"] and ["god", "dog"] are two groups of anagrams.

Example 2 · Example:

Input: string_list = ["no", "on", "is"]
Output: [["no", "on"], ["is"]]
Explanation: ["no", "on"] form an anagram group, and ["is"] forms an individual group.

Constraints:

  • 1 <= N <= 104
  • 1 <= string_list[i].length <= 10
  • string_list[i] consists of lowercase English letters.

What You'll Learn

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

  • Group string equivalence classes using hash tables.
  • Formulate canonical string representations.
  • Optimize string signature generation from O(K log K) to O(K).

Pattern Recognition Trigger

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

Signals to Look For:

  • Partitioning words into anagram equivalence classes.
  • Grouping items by invariant permutations.

Algorithmic Decision Tree:

  • Hash Map Grouping
  • Canonical Signature Indexing

Connected Patterns:

Group AnagramsValid AnagramFind All Anagrams in a String

1. Pairwise Anagram Comparison with Visited Array

Intuition

Maintain a boolean visited array. For each unvisited string i: create a group with string_list[i], and for every j > i: if string_list[j] is an anagram of string_list[i], add to group and mark visited.

When to apply: Baseline comparison.

Algorithm

  1. Initialize visited = [false] * N, res = [].
  2. For i from 0 to N - 1:
  3. If visited[i]: continue.
  4. group = [string_list[i]]; visited[i] = true.
  5. For j from i + 1 to N - 1:
  6. If !visited[j] && isAnagram(string_list[i], string_list[j]):
  7. group.push(string_list[j]); visited[j] = true.
  8. res.push(group).
  9. Return res.

Pairwise Anagram Comparison with Visited Array

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [act, god, cat, dog, tac]
Current operationSTEP 1 OF 6
Observation: Track visited boolean array of size 5
Visual state
Values and pointers at this exact step
array
S
act
god
cat
dog
tac
0
↑ GROUP 1: 'act'
1
2
3
4
Variables at this step
group1
["act"]
visited
[true,false,false,false,false]
Check / comparison
First unvisited word is 'act'. Compare pairwise with remaining words.
Decision / next transition
Initialize Group 1: ['act']. Mark index 0 visited.
Why this step matters

Observation: Track visited boolean array of size 5. Unvisited word at index 0 is 'act'.

Decision: Start Group 1 with 'act'.

Invariant: Words assigned to groups are marked visited to prevent duplicate membership.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 bool isAnagram(const std::string& a, const std::string& b) {
8 if (a.size() != b.size()) return false;
9 int count[26] = {0};
10 for (char c : a) count[c - 'a']++;
11 for (char c : b) count[c - 'a']--;
12 for (int x : count) if (x != 0) return false;
13 return true;
14 }
15public:
16 std::vector<std::vector<std::string>> anagrams(std::vector<std::string>& string_list) {
17 int n = string_list.size();
18 std::vector<bool> visited(n, false);
19 std::vector<std::vector<std::string>> res;
20
21 for (int i = 0; i < n; ++i) {
22 if (visited[i]) continue;
23 std::vector<std::string> group;
24 group.push_back(string_list[i]);
25 visited[i] = true;
26
27 for (int j = i + 1; j < n; ++j) {
28 if (!visited[j] && isAnagram(string_list[i], string_list[j])) {
29 group.push_back(string_list[j]);
30 visited[j] = true;
31 }
32 }
33 res.push_back(group);
34 }
35 return res;
36 }
37};
38
39int main() {
40 Solution sol;
41 std::vector<std::string> list = {"act", "god", "cat", "dog", "tac"};
42 auto ans = sol.anagrams(list);
43 for (const auto& g : ans) {
44 for (const auto& w : g) 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) — N2 pairwise checks each comparing K characters.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Using frequency tuples achieves strictly O(N * K) linear time without sorting.

Grouping strings directly into hash map value arrays.

2. Hash Map with Sorted Key

Intuition

For each string in string_list: make a copy, sort its characters to form key. Insert string into map[key]. Collect all values from map into a 2D result list.

When to apply: Standard canonical implementation.

Algorithm

  1. Initialize map = {}.
  2. For each str in string_list:
  3. key = sort(str).
  4. map[key].push(str).
  5. Return map.values().

Hash Map with Sorted Key

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [act, god, cat, dog, tac]
Current operationSTEP 1 OF 6
Observation: Initialize hash map
Visual state
Values and pointers at this exact step
array
S
act
god
cat
dog
tac
0
↑ SORT 'act' -> 'act'
1
2
3
4
Variables at this step
map
{"act":["act"]}
Check / comparison
Sort 'act' -> 'act'. Insert map['act'] = ['act'].
Decision / next transition
Map: { 'act': ['act'] }.
Why this step matters

Observation: Initialize hash map. Sort first word 'act' -> 'act'.

Decision: Insert key 'act' with list ['act'].

Invariant: Identical sorted representations serve as canonical hash 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>> anagrams(std::vector<std::string>& string_list) {
10 std::unordered_map<std::string, std::vector<std::string>> groups;
11 for (const auto& str : string_list) {
12 std::string key = str;
13 std::sort(key.begin(), key.end());
14 groups[key].push_back(str);
15 }
16
17 std::vector<std::vector<std::string>> res;
18 for (auto& pair : groups) {
19 res.push_back(std::move(pair.second));
20 }
21 return res;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::vector<std::string> list = {"act", "god", "cat", "dog", "tac"};
28 auto ans = sol.anagrams(list);
29 for (const auto& g : ans) {
30 for (const auto& w : g) std::cout << w << " ";
31 std::cout << "| ";
32 }
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N * K log K) — Sorting N strings of length K takes N * K log K time.
  • Space complexity: O(N * K)

3. Frequency Signature Hash Map (Optimal O(N * K))

Intuition

For each string, compute its 26-element character count array. Format the count array as a delimited string (e.g. "1#0#1#0..."). Use this count signature as the hash map key.

When to apply: The standard gold standard solution achieving linear time without sorting.

Algorithm

  1. Initialize map = {}.
  2. For each str in string_list:
  3. count = [0] * 26.
  4. For c in str: count[c - 'a']++.
  5. key = count.join('#').
  6. map[key].push(str).
  7. Return map.values().

Sorted Tuple Canonical Bucket Aggregation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [act, god, cat, dog, tac]
Current operationSTEP 1 OF 6
Observation: Read words[0] = "act"
Visual state
Values and pointers at this exact step
array
S
act
god
cat
dog
tac
0
↑ words[0] = "act"
1
2
3
4
Variables at this step
word
act
sortedKey
act
buckets
{"act":["act"]}
Why this step matters

Observation: Read words[0] = "act". Sort characters alphabetically: 'a','c','t' -> key "act".

Decision: Initialize bucket for key "act" with ["act"].

Invariant: All anagrams share the identical alphabetically sorted key.

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>> anagrams(std::vector<std::string>& string_list) {
9 std::unordered_map<std::string, std::vector<std::string>> groups;
10
11 for (const auto& str : string_list) {
12 int count[26] = {0};
13 for (char c : str) count[c - 'a']++;
14
15 std::string key = "";
16 for (int i = 0; i < 26; ++i) {
17 key += std::to_string(count[i]) + "#";
18 }
19 groups[key].push_back(str);
20 }
21
22 std::vector<std::vector<std::string>> res;
23 for (auto& pair : groups) {
24 res.push_back(std::move(pair.second));
25 }
26 return res;
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::string> list = {"act", "god", "cat", "dog", "tac"};
33 auto ans = sol.anagrams(list);
34 for (const auto& g : ans) {
35 for (const auto& w : g) std::cout << w << " ";
36 std::cout << "| ";
37 }
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N * K) strictly — Linear time processing: O(K) counting per word across N words.
  • 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 Anagram ComparisonO(N^2 * K)O(N)No hash map needed.Quadratic time complexity, too slow.
2.Hash Map with Sorted KeyO(N * K log K)O(N * K)Simple, highly readable, standard solution.Sort overhead per string.
3.Hash Map with 26-Count Tuple Signature (Optimal)OptimalO(N * K)O(N * K)Strictly linear time in total character count.Key formatting string overhead.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using delimiters missing in key creation, causing count '1, 10' to collide with '11, 0'.

Pitfall 2:

Not handling strings of length 1.

Crucial Edge Cases to Validate:

  • Single string in list: Returns [[string_list[0]]].
  • All strings are unique with no anagrams: Returns list of single-element lists.
  • All strings are anagrams of each other: Returns single group with all strings.

Interview Tips & Best Practices

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

  1. State both the sorted string key approach and the 26-count tuple approach.
  2. Explain delimiter safety when serializing frequency keys.

Quick Comprehension Check

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

1.Why is a delimiter like # required when serializing character count arrays into strings?

Back to DSA Sheet