Group Anagrams Using Hash Map in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an anagram?

An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once. For example, "listen" and "silent" are anagrams.

beginner

Why do we use a hash map to group anagrams?

A hash map helps group anagrams by using a key that represents the sorted letters of the word. All words with the same sorted key are anagrams and stored together in the map.

beginner

How do you create a key for each word to group anagrams?

Sort the letters of the word alphabetically and use the sorted string as the key. For example, "eat" becomes "aet". All words with key "aet" are anagrams.

intermediate

What is the time complexity of grouping anagrams using a hash map?

The time complexity is O(N * K log K), where N is the number of words and K is the maximum length of a word. Sorting each word takes O(K log K), done for all N words.

beginner

What does the final output look like after grouping anagrams?

The output is a list of lists, where each inner list contains words that are anagrams of each other. For example: [["eat", "tea", "ate"], ["bat"]].

What is the key used in the hash map to group anagrams?

A Sorted letters of the word

B Length of the word

C First letter of the word

D Number of vowels in the word

The key is the sorted letters of the word, so all anagrams share the same key.

Which data structure is best for grouping anagrams efficiently?

A Hash Map

B Stack

C Queue

D Linked List

A hash map allows quick grouping by keys representing sorted words.

What is the main operation done on each word before using it as a key?

A Counting vowels

B Reversing the word

C Sorting its letters

D Converting to uppercase

Sorting the letters ensures all anagrams have the same key.

If the input words are ["bat", "tab", "eat"], how many groups of anagrams will be formed?

A 1

B 2

C 3

D None

"bat" and "tab" form one group; "eat" is alone, so two groups total.

What is the output format after grouping anagrams?

A Dictionary with counts

B Single string

C Array of integers

D List of lists of strings

The output is a list where each element is a list of anagram words.

Explain step-by-step how to group anagrams using a hash map.

Think about how sorting helps identify anagrams and how the hash map stores groups.

Describe the time complexity of grouping anagrams and why sorting each word affects it.

Focus on the sorting step inside the loop over all words.

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