Group Anagrams Using Hash Map in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Grouping Anagrams by Sorted Key

What is the output of the following C++ code that groups anagrams using a hash map with sorted strings as keys?

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

int main() {
    std::vector<std::string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    std::unordered_map<std::string, std::vector<std::string>> groups;

    for (auto& word : words) {
        std::string key = word;
        std::sort(key.begin(), key.end());
        groups[key].push_back(word);
    }

    for (auto& pair : groups) {
        std::cout << "[";
        for (auto& w : pair.second) {
            std::cout << w << ", ";
        }
        std::cout << "]\n";
    }
    return 0;
}

A

[bat, ]
[tan, nat, ]
[eat, tea, ate, ]

B

[eat, tea, ate, ]
[tan, nat, ]
[bat, ]

C

[eat, ate, tea, ]
[bat, ]
[tan, nat, ]

D

[bat, ]
[eat, tea, ate, ]
[tan, nat, ]

💡 Hint

Focus on how the sorted key groups the anagrams together.

The code sorts each word to create a key. All anagrams share the same sorted key, so they group together. The output order depends on the unordered_map iteration order, but the groups contain the correct anagrams.

🧠 Conceptual

intermediate

Why Use Sorted Strings as Keys in Grouping Anagrams?

Why do we use the sorted version of a string as the key in a hash map to group anagrams?

A Because sorted strings are unique identifiers for anagram groups.

B Because sorting strings makes them shorter and easier to store.

C Because sorted strings are always the same length as original strings.

D Because sorting strings removes duplicate characters.

💡 Hint

Think about what makes anagrams similar.

Anagrams have the same characters in different orders. Sorting puts characters in a fixed order, so all anagrams become the same sorted string, which can be used as a unique key.

🔧 Debug

advanced

Identify the Error in Grouping Anagrams Code

What error will this C++ code produce when grouping anagrams using a hash map?

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

int main() {
    std::vector<std::string> words = {"bat", "tab", "eat"};
    std::unordered_map<std::string, std::vector<std::string>> groups;

    for (auto word : words) {
        std::string key = word;
        std::sort(word.begin(), word.end());
        groups[word].push_back(word);
    }

    for (auto& pair : groups) {
        std::cout << pair.first << ": ";
        for (auto& w : pair.second) {
            std::cout << w << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

A Runtime error because 'word' is modified but used incorrectly as key and value.

B Compilation error due to modifying a const string.

C Logical error: groups keys are sorted words but values are sorted words, losing original words.

D No error; outputs grouped anagrams correctly.

💡 Hint

Check what is stored as keys and values after sorting.

The code sorts 'word' and uses it both as key and value, so original words are lost. The groups contain sorted words, not original words, causing logical error in output.

🚀 Application

advanced

Number of Groups Formed by Grouping Anagrams

Given the list of words: ["listen", "silent", "enlist", "google", "gooegl", "abc", "cab"], how many groups will be formed when grouping anagrams using a hash map with sorted keys?

A 4

B 6

C 5

D 3

💡 Hint

Group words by their sorted character sequences.

Groups are: [listen, silent, enlist], [google, gooegl], [abc, cab]. So total 3 groups.

❓ Predict Output

expert

Output of Group Anagrams with Frequency Count Key

What is the output of the following C++ code that groups anagrams using a frequency count array as the key in a hash map?

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <array>

struct Key {
    std::array<int, 26> count{};
    bool operator==(const Key& other) const {
        return count == other.count;
    }
};

namespace std {
    template<>
    struct hash<Key> {
        size_t operator()(const Key& k) const {
            size_t h = 0;
            for (int c : k.count) {
                h = h * 31 + c;
            }
            return h;
        }
    };
}

int main() {
    std::vector<std::string> words = {"abc", "bca", "cab", "xyz", "zyx", "zxy", "aabb"};
    std::unordered_map<Key, std::vector<std::string>> groups;

    for (auto& word : words) {
        Key k;
        for (char ch : word) {
            k.count[ch - 'a']++;
        }
        groups[k].push_back(word);
    }

    for (auto& pair : groups) {
        std::cout << "[";
        for (auto& w : pair.second) {
            std::cout << w << ", ";
        }
        std::cout << "]\n";
    }
    return 0;
}

A

[abc, bca, cab, ]
[xyz, zyx, zxy, ]
[aabb, ]

B

[abc, bca, cab, ]
[aabb, ]
[xyz, zyx, zxy, ]

C

[xyz, zyx, zxy, ]
[abc, bca, cab, ]
[aabb, ]

D

[aabb, ]
[xyz, zyx, zxy, ]
[abc, bca, cab, ]

💡 Hint

Frequency count keys group anagrams by character counts.

Words with same character counts form groups. The groups are: [abc, bca, cab], [xyz, zyx, zxy], and [aabb]. The order depends on unordered_map iteration but matches option A.

Practice

1. What is the main idea behind grouping anagrams using a hash map?

easy

A. Use sorted strings as keys to group words with the same characters

B. Use the length of the string as the key to group words

C. Use the first character of the string as the key

D. Use the last character of the string as the key

Solution

1. Step 1: Understand anagram grouping

   Anagrams have the same characters in different orders, so sorting the string gives a unique key for all anagrams.

2. Step 2: Use sorted string as hash map key

   By sorting each word and using it as a key, all anagrams map to the same key and can be grouped together.

3. Final Answer:

   Use sorted strings as keys to group words with the same characters -> Option A

4. Quick Check:

   Sorted string key = group anagrams [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Using string length as key misses different anagrams
• Using first or last character groups unrelated words
• Not sorting strings before using as keys

2. Which of the following C++ code snippets correctly declares a hash map to group anagrams where the key is a string and the value is a vector of strings?

easy

A. std::unordered_map anagramGroups;

B. std::map> anagramGroups;

C. std::unordered_map> anagramGroups;

D. std::unordered_map anagramGroups;

Solution

1. Step 1: Identify key and value types

   The key should be a string (sorted word), and the value should be a vector of strings (group of anagrams).

2. Step 2: Match correct declaration

   std::unordered_map> anagramGroups; uses unordered_map with key as string and value as vector<string>, which is correct for grouping anagrams.

3. Final Answer:

   std::unordered_map> anagramGroups; -> Option C

4. Quick Check:

   Key=string, Value=vector<string> [OK]

Hint: Use unordered_map for grouping [OK]

Common Mistakes:

• Using int as key instead of string
• Using vector<char> as key (not hashable)
• Using string as value instead of vector<string>

3. What is the output of the following C++ code snippet?

std::vector words = {"eat", "tea", "tan", "ate", "nat", "bat"};
std::unordered_map> groups;
for (auto &word : words) {
    std::string sortedWord = word;
    std::sort(sortedWord.begin(), sortedWord.end());
    groups[sortedWord].push_back(word);
}
for (auto &pair : groups) {
    std::cout << "Group: ";
    for (auto &w : pair.second) std::cout << w << " ";
    std::cout << std::endl;
}

medium

A. Group: eat tea
Group: tan bat
Group: ate nat

B. Group: eat tea ate
Group: tan nat
Group: bat

C. Group: ate tea
Group: bat tan
Group: eat nat

D. Group: eat tan bat
Group: tea nat ate

Solution

1. Step 1: Sort each word and group by sorted key

   "eat", "tea", "ate" all sort to "aet" so grouped together; "tan", "nat" sort to "ant"; "bat" sorts to "abt".

2. Step 2: Print groups

   Groups printed are: "eat tea ate", "tan nat", and "bat".

3. Final Answer:

   Group: eat tea ate Group: tan nat Group: bat -> Option B

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

Hint: Sort words, group by sorted key, print groups [OK]

Common Mistakes:

• Not sorting words before grouping
• Mixing groups by original word order
• Printing keys instead of grouped words

4. Identify the error in the following code snippet that tries to group anagrams:

std::vector words = {"abc", "bca", "cab"};
std::unordered_map> groups;
for (auto word : words) {
    std::string key = word;
    std::sort(word.begin(), word.end());
    groups[key].push_back(word);
}

medium

A. Sorting is done on 'word' but 'key' is used as map key, causing wrong grouping

B. The vector 'words' is not initialized correctly

C. The map should use vector<char> as key instead of string

D. The loop variable should be a reference to avoid copying

Solution

1. Step 1: Analyze sorting and key usage

   The code sorts 'word' but uses 'key' (unsorted) as the map key, so grouping is incorrect.

2. Step 2: Correct usage

   Sort 'key' and use it as the map key to group anagrams properly.

3. Final Answer:

   Sorting is done on 'word' but 'key' is used as map key, causing wrong grouping -> Option A

4. Quick Check:

   Sort key before using in map [OK]

Hint: Sort the key string, not the original word [OK]

Common Mistakes:

• Sorting wrong variable before using as key
• Using unsorted string as map key
• Ignoring reference vs copy in loop

5. Given a list of strings, how would you modify the grouping anagrams approach to handle case-insensitive grouping (e.g., "Eat" and "tea" should be grouped together)?

hard

A. Sort strings without changing case

B. Use the original string as key without any changes

C. Group by string length only

D. Convert each string to lowercase before sorting and using as key

Solution

1. Step 1: Normalize case for consistent keys

   Convert each string to lowercase so that case differences do not affect grouping.

2. Step 2: Sort the lowercase string and use as key

   Sorting the lowercase string ensures all case variants of anagrams map to the same key.

3. Step 3: Group anagrams using normalized keys

   Use the lowercase sorted string as the hash map key to group anagrams case-insensitively.

4. Final Answer:

   Convert each string to lowercase before sorting and using as key -> Option D

5. Quick Check:

   Lowercase + sort = case-insensitive grouping [OK]

Hint: Lowercase strings before sorting to ignore case [OK]

Common Mistakes:

• Not normalizing case before grouping
• Using original case strings as keys
• Grouping by length or unsorted strings