Group Anagrams Using Hash Map in DSA C

Mental Model

Group words that have the same letters by sorting their letters and using that as a key.

Analogy: Imagine sorting letters of each word like arranging colored beads in order; words with the same bead order belong to the same group.

words: [eat, tea, tan, ate, nat, bat]
keys:  [aet, aet, ant, aet, ant, abt]

Hash Map:
{
  "aet" -> [eat, tea, ate]
  "ant" -> [tan, nat]
  "abt" -> [bat]
}

Dry Run Walkthrough

Input: words: [eat, tea, tan, ate, nat, bat]

Goal: Group words that are anagrams together using a hash map keyed by sorted letters.

Step 1: Take first word 'eat', sort letters to get 'aet', add 'eat' to group 'aet'

{ "aet": [eat] }

Why: Sorting letters creates a key that groups anagrams together

Step 2: Take second word 'tea', sort letters to get 'aet', add 'tea' to group 'aet'

{ "aet": [eat, tea] }

Why: Words with same sorted letters belong to same group

Step 3: Take third word 'tan', sort letters to get 'ant', add 'tan' to group 'ant'

{ "aet": [eat, tea], "ant": [tan] }

Why: New sorted key creates a new group

Step 4: Take fourth word 'ate', sort letters to get 'aet', add 'ate' to group 'aet'

{ "aet": [eat, tea, ate], "ant": [tan] }

Why: Add to existing group with same key

Step 5: Take fifth word 'nat', sort letters to get 'ant', add 'nat' to group 'ant'

{ "aet": [eat, tea, ate], "ant": [tan, nat] }

Why: Add to existing group with same key

Step 6: Take sixth word 'bat', sort letters to get 'abt', add 'bat' to group 'abt'

{ "aet": [eat, tea, ate], "ant": [tan, nat], "abt": [bat] }

Why: New key creates new group

Result:

{ "aet": [eat, tea, ate], "ant": [tan, nat], "abt": [bat] }

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Node for linked list of words
typedef struct WordNode {
    char *word;
    struct WordNode *next;
} WordNode;

// Hash map entry
typedef struct Entry {
    char *key; // sorted letters
    WordNode *words; // linked list of words
    struct Entry *next;
} Entry;

#define HASH_SIZE 101

// Hash map with chaining
typedef struct HashMap {
    Entry *buckets[HASH_SIZE];
} HashMap;

unsigned int hash_func(const char *str) {
    unsigned int hash = 0;
    while (*str) {
        hash = hash * 31 + (unsigned char)(*str++);
    }
    return hash % HASH_SIZE;
}

// Create a new word node
WordNode *create_word_node(const char *word) {
    WordNode *node = malloc(sizeof(WordNode));
    node->word = strdup(word);
    node->next = NULL;
    return node;
}

// Create a new entry
Entry *create_entry(const char *key, const char *word) {
    Entry *entry = malloc(sizeof(Entry));
    entry->key = strdup(key);
    entry->words = create_word_node(word);
    entry->next = NULL;
    return entry;
}

// Insert word into hash map
void insert(HashMap *map, const char *word) {
    int len = strlen(word);
    char *sorted = malloc(len + 1);
    strcpy(sorted, word);
    // Sort letters to get key
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (sorted[i] > sorted[j]) {
                char temp = sorted[i];
                sorted[i] = sorted[j];
                sorted[j] = temp;
            }
        }
    }

    unsigned int index = hash_func(sorted);
    Entry *entry = map->buckets[index];

    // Search for existing key
    while (entry) {
        if (strcmp(entry->key, sorted) == 0) {
            // Add word to this entry's list
            WordNode *wn = create_word_node(word);
            wn->next = entry->words;
            entry->words = wn;
            free(sorted);
            return;
        }
        entry = entry->next;
    }

    // Key not found, create new entry
    Entry *new_entry = create_entry(sorted, word);
    new_entry->next = map->buckets[index];
    map->buckets[index] = new_entry;
    free(sorted);
}

// Print groups of anagrams
void print_groups(HashMap *map) {
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry *entry = map->buckets[i];
        while (entry) {
            WordNode *wn = entry->words;
            printf("[");
            while (wn) {
                printf("%s", wn->word);
                if (wn->next) printf(", ");
                wn = wn->next;
            }
            printf("]\n");
            entry = entry->next;
        }
    }
}

// Free memory
void free_map(HashMap *map) {
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry *entry = map->buckets[i];
        while (entry) {
            Entry *next_entry = entry->next;
            free(entry->key);
            WordNode *wn = entry->words;
            while (wn) {
                WordNode *next_wn = wn->next;
                free(wn->word);
                free(wn);
                wn = next_wn;
            }
            free(entry);
            entry = next_entry;
        }
    }
}

int main() {
    const char *words[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    int n = sizeof(words) / sizeof(words[0]);

    HashMap map = {0};

    for (int i = 0; i < n; i++) {
        insert(&map, words[i]);
    }

    print_groups(&map);

    free_map(&map);
    return 0;
}

for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (sorted[i] > sorted[j]) { char temp = sorted[i]; sorted[i] = sorted[j]; sorted[j] = temp; } } }

sort letters of word to create key for grouping anagrams

while (entry) { if (strcmp(entry->key, sorted) == 0) { add word to entry's word list; return; } entry = entry->next; }

search for existing group with same sorted key

create new entry with key and word; insert at bucket head

create new group if key not found

for each word in input array, insert into hash map

build groups by processing all words

print all groups by iterating hash map buckets and word lists

output grouped anagrams

Output

[ate, tea, eat]

[nat, tan]

[bat]

Complexity Analysis

Time: O(n * k^2) because for each of the n words, sorting k letters takes O(k^2) with simple sort

Space: O(n * k) because storing all words and keys in hash map requires space proportional to input size

vs Alternative: Better than comparing each pair of words O(n^2 * k), hash map groups in near linear time

Edge Cases

empty input array

no groups printed, program runs without error

DSA C

for (int i = 0; i < n; i++) { insert(&map, words[i]); }

words with single letter

each letter forms its own group or groups if repeated

DSA C

sorting loop handles length 1 correctly

words with duplicates (e.g., 'aab', 'aba')

correctly grouped together because sorted key is same

DSA C

sorting and key comparison lines

When to Use This Pattern

When you need to group words that are anagrams, use a hash map keyed by sorted letters to quickly collect groups.

Common Mistakes

Mistake: Using the original word as key instead of sorted letters
Fix: Sort the letters of each word before using as key

Mistake: Not handling collisions in hash map chaining
Fix: Use linked lists to handle multiple entries in same bucket

Summary

Groups words that are anagrams by sorting letters and using a hash map keyed by sorted letters.

Use when you want to collect all anagrams together efficiently from a list of words.

The key insight is that anagrams share the same sorted letter sequence, which can be used as a unique group key.

Practice

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

easy

A. Use the length of words as keys to group anagrams

B. Store words in a list without any sorting or grouping

C. Group words by their first character only

D. Use sorted strings as keys to group words with the same letters

Solution

1. Step 1: Understand anagrams and their properties

   Anagrams are words made of the same letters in any order, so sorting letters gives a unique key for each group.

2. Step 2: Use sorted strings as hash map keys

   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 letters -> Option D

4. Quick Check:

   Sorted word keys group anagrams [OK]

Hint: Sort each word and use as key to group anagrams [OK]

Common Mistakes:

• Grouping by word length only
• Using first character as key
• Not sorting words before grouping

2. Which of the following is the correct way to declare a hash map (dictionary) in C for grouping anagrams?

easy

A. map anagramGroups;

B. unordered_map anagramGroups;

C. unordered_map anagramGroups;

D. vector<string> anagramGroups;

Solution

1. Step 1: Identify the data types needed for grouping anagrams

   We need a map from a string key (sorted word) to a list of strings (anagrams).

2. Step 2: Choose the correct C++ STL container

   unordered_map fits this need perfectly.

3. Final Answer:

   unordered_map anagramGroups; -> Option B

4. Quick Check:

   Map from string to vector<string> groups anagrams [OK]

Hint: Use unordered_map for grouping anagrams [OK]

Common Mistakes:

• Using map which mismatches key and value types
• Using vector<string> alone without mapping keys
• Using unordered_map which is unrelated

3. What is the output of the following C++ code snippet? vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"}; unordered_map groups; for (auto &word : words) { string sortedWord = word; sort(sortedWord.begin(), sortedWord.end()); groups[sortedWord].push_back(word); } for (auto &pair : groups) { sort(pair.second.begin(), pair.second.end()); for (auto &w : pair.second) cout << w << " "; cout << endl; }

medium

A. bat
nat tan
eat tea ate

B. eat tea ate
bat
tan nat

C. tea ate eat
bat
tan nat

D. ate eat tea
bat
nat tan

Solution

1. Step 1: Group words by sorted keys

   Words "eat", "tea", "ate" all sort to "aet" and group together; "tan", "nat" to "ant"; "bat" to "abt".

2. Step 2: Sort each group and print

   Each group is sorted alphabetically before printing: "ate eat tea", "bat", "nat tan".

3. Final Answer:

   bat nat tan eat tea ate -> Option A

4. Quick Check:

   Sorted keys group anagrams; groups sorted before print [OK]

Hint: Sort words and groups before printing for consistent output [OK]

Common Mistakes:

• Not sorting groups before printing
• Printing groups in wrong order
• Confusing sorted keys with original words

4. Identify the bug in this C++ code for grouping anagrams: vector<string> words = {"abc", "bca", "cab"}; unordered_map groups; for (auto word : words) { string key = word; sort(word.begin(), word.end()); groups[key].push_back(word); }

medium

A. Sorting is done on 'word' but key uses unsorted string

B. Using unordered_map instead of map causes error

C. Loop variable should be reference to avoid copies

D. Missing initialization of groups map

Solution

1. Step 1: Check how key and sorted string are assigned

   Key is assigned before sorting, so key is unsorted original word.

2. Step 2: Sorting is done on 'word' but key remains unsorted

   Groups use unsorted key, so anagrams won't group correctly.

3. Final Answer:

   Sorting is done on 'word' but key uses unsorted string -> Option A

4. Quick Check:

   Key must be sorted string for correct grouping [OK]

Hint: Sort string before assigning key for hash map [OK]

Common Mistakes:

• Assigning key before sorting
• Sorting wrong variable
• Not using reference in loop (less critical here)

5. Given a list of words, how can you modify the hash map grouping approach to handle case-insensitive anagrams (e.g., "Eat" and "tea" grouped together)?

hard

A. Group words by their first letter ignoring case

B. Use word length as key instead of sorted string

C. Convert all words to lowercase before sorting and grouping

D. Sort words without changing case and group normally

Solution

1. Step 1: Understand case-insensitive grouping

   "Eat" and "tea" differ in case but are anagrams ignoring case.

2. Step 2: Normalize words by converting to lowercase before sorting

   This ensures keys match regardless of original case.

3. Final Answer:

   Convert all words to lowercase before sorting and grouping -> Option C

4. Quick Check:

   Lowercase normalization groups case-insensitive anagrams [OK]

Hint: Lowercase words before sorting to group case-insensitive anagrams [OK]

Common Mistakes:

• Grouping by length only
• Ignoring case normalization
• Sorting without case conversion