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 putting puzzle pieces in order, then putting all puzzles with the same picture into one box.

words: ["eat", "tea", "tan", "ate", "nat", "bat"]
keys:  ["aet", "aet", "ant", "aet", "ant", "abt"]
HashMap:
"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

Dry Run Walkthrough

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

Goal: Group all words that are anagrams together in lists

Step 1: Take first word "eat", sort letters to get key "aet", add "eat" to group under "aet"

"aet" -> ["eat"]

Why: Sorting letters creates a unique key for anagrams

Step 2: Take second word "tea", sort letters to get key "aet", add "tea" to group under "aet"

"aet" -> ["eat", "tea"]

Why: Words with same sorted letters belong to same group

Step 3: Take third word "tan", sort letters to get key "ant", add "tan" to group under "ant"

"aet" -> ["eat", "tea"]
"ant" -> ["tan"]

Why: New key means new group

Step 4: Take fourth word "ate", sort letters to get key "aet", add "ate" to group under "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 key "ant", add "nat" to group under "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 key "abt", add "bat" to group under "abt"

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

Why: New key means new group

Result:

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]
Grouped anagrams: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var map = new Dictionary<string, List<string>>();
        foreach (var word in strs) {
            var chars = word.ToCharArray();
            Array.Sort(chars); // sort letters to get key
            var key = new string(chars);
            if (!map.ContainsKey(key)) {
                map[key] = new List<string>(); // create new group
            }
            map[key].Add(word); // add word to group
        }
        return map.Values.Cast<IList<string>>().ToList();
    }
}

class Program {
    static void Main() {
        var input = new string[] {"eat", "tea", "tan", "ate", "nat", "bat"};
        var solution = new Solution();
        var groups = solution.GroupAnagrams(input);
        foreach (var group in groups) {
            Console.WriteLine(string.Join(", ", group));
        }
    }
}

Array.Sort(chars); // sort letters to get key

sort letters of current word to create a unique key for anagrams

if (!map.ContainsKey(key)) { map[key] = new List<string>(); // create new group }

check if group exists for this key, if not create it

map[key].Add(word); // add word to group

add current word to its anagram group

Output

eat, tea, ate

tan, nat

bat

Complexity Analysis

Time: O(n * k log k) because we sort each of the n words of length k

Space: O(n * k) because we store all words grouped by their sorted keys

vs Alternative: Naive approach compares each word with every other word O(n^2 * k), this uses hashing to reduce comparisons

Edge Cases

empty input array

returns empty list with no groups

DSA C#

foreach (var word in strs) { ... } handles zero iterations gracefully

words with single character

groups single letters correctly as keys are just the letter itself

DSA C#

Array.Sort(chars); works even if chars length is 1

all words are identical

all words grouped under one key

DSA C#

map[key].Add(word); adds all identical words to same group

When to Use This Pattern

When you need to group words that are made of the same letters, use sorting as a key and a hash map to collect groups efficiently.

Common Mistakes

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

Mistake: Not checking if the key exists before adding to the group
Fix: Check if key exists in map, if not create a new list before adding

Summary

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

Use when you want to find all sets of words that have the same letters.

Sorting letters creates a unique key that identifies anagram groups.

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 letters

B. Use the length of the word as the key to group anagrams

C. Use the first letter of the word as the key to group anagrams

D. Use the last letter of the word as the key to group anagrams

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted string as key

   Sorting letters of each word gives a unique key for all anagrams.

3. Final Answer:

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

4. Quick Check:

   Sorted string key groups anagrams [OK]

Hint: Sort each word and use it as key in hash map [OK]

Common Mistakes:

• Using word length as key causes wrong grouping
• Using first or last letter misses many anagrams
• Not sorting letters before using as key

2. Which of the following C# code snippets correctly initializes a hash map to group anagrams?

easy

A. var map = new Dictionary();

B. var map = new List>();

C. var map = new Dictionary();

D. var map = new Dictionary();

Solution

1. Step 1: Identify correct dictionary type

   We need keys as strings (sorted words) and values as lists of strings (anagrams).

2. Step 2: Check each option

   var map = new Dictionary(); uses Dictionary which fits the requirement.

3. Final Answer:

   var map = new Dictionary(); -> Option A

4. Quick Check:

   Dictionary with string keys and list values [OK]

Hint: Use Dictionary for grouping anagrams [OK]

Common Mistakes:

• Using List of dictionaries instead of dictionary
• Using wrong key or value types
• Using Dictionary which can't group anagrams

3. What is the output of the following C# code?

var strs = new string[] {"eat", "tea", "tan", "ate", "nat", "bat"};
var map = new Dictionary();
foreach (var s in strs) {
  var key = String.Concat(s.OrderBy(c => c));
  if (!map.ContainsKey(key)) map[key] = new List<string>();
  map[key].Add(s);
}
foreach (var group in map.Values) {
  Console.WriteLine(string.Join(", ", group));
}

medium

A. "eat, tea\nate, tan\nbat, nat"

B. "eat, tan, bat\ntea, ate, nat"

C. "eat, tea, ate\ntan, nat\nbat"

D. "eat, tea, ate, tan, nat, bat"

Solution

1. Step 1: Sort each word to find keys

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

2. Step 2: Group words by keys and print

   Groups are ["eat", "tea", "ate"], ["tan", "nat"], ["bat"]. Printed line by line.

3. Final Answer:

   "eat, tea, ate\ntan, nat\nbat" -> Option C

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

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

Common Mistakes:

• Printing all words in one line
• Grouping by unsorted words
• Mixing groups incorrectly

4. Identify the bug in this C# code snippet for grouping anagrams:

var map = new Dictionary();
foreach (var s in strs) {
  var key = s.OrderBy(c => c).ToString();
  if (!map.ContainsKey(key)) map[key] = new List<string>();
  map[key].Add(s);
}

medium

A. Not checking if key exists before adding

B. Missing initialization of map dictionary

C. Using List<string> instead of List<char> for values

D. Using ToString() on IEnumerable<char> does not produce sorted string key

Solution

1. Step 1: Understand s.OrderBy(c => c)

   This returns IEnumerable<char>, not a string.

2. Step 2: Using ToString() on IEnumerable<char>

   ToString() returns type name, not sorted string key. Need to join chars to string.

3. Final Answer:

   Using ToString() on IEnumerable<char> does not produce sorted string key -> Option D

4. Quick Check:

   Use String.Concat or new string() to convert chars to string [OK]

Hint: Convert sorted chars to string with String.Concat, not ToString() [OK]

Common Mistakes:

• Calling ToString() on IEnumerable<char> expecting string
• Not initializing dictionary before use
• Ignoring key existence check

5. Given a list of strings, how would you modify the grouping anagrams code to ignore case differences (e.g., "Eat" and "tea" should be grouped)?

hard

A. Group by string length only

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

C. Sort strings but keep original case for keys

D. Use the original string as key without sorting

Solution

1. Step 1: Normalize case for grouping

   Convert each string to lowercase to treat "Eat" and "tea" the same.

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

   Sorting lowercase letters groups anagrams ignoring case.

3. Final Answer:

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

4. Quick Check:

   Lowercase + sort = case-insensitive grouping [OK]

Hint: Lowercase strings before sorting for case-insensitive grouping [OK]

Common Mistakes:

• Sorting without case normalization
• Using original case keys causing separate groups
• Grouping by length which is insufficient