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

Recall & Review

beginner

What is an anagram?

An anagram is a word or phrase made by rearranging the letters of another word or phrase, using all the original letters exactly once.

beginner

Why do we use a hash map to group anagrams?

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

beginner

How do you create the key for the hash map when grouping anagrams?

Sort the characters of the word alphabetically and use the sorted string as the key in the hash map.

intermediate

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

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 (due to sorting each word).

beginner

What data structure is used to store the grouped anagrams before returning the result?

A list of lists (or array of arrays) is used to store groups of anagrams collected from the hash map values.

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

A The original word itself

B The length of the word

C The first character of the word

D The sorted string of the word

The sorted string of the word is used as the key because all anagrams share the same sorted characters.

Which data structure is best to store groups of anagrams during grouping?

A Hash map with sorted string keys and list of words as values

B Stack

C Queue

D Binary tree

A hash map with sorted string keys and lists of words as values efficiently groups anagrams.

What is the main operation done on each word to find its group?

A Count vowels

B Reverse the word

C Sort the characters of the word

D Convert to uppercase

Sorting the characters helps create a uniform key for all anagrams.

If the input list has 5 words each of length 3, what is the approximate time complexity to group anagrams?

A O(5 * 3 log 3)

B O(5 + 3)

C O(5 * 3)

D O(5^3)

Time complexity is O(N * K log K), here N=5 and K=3, so O(5 * 3 log 3).

What will be the output grouping for input: ["eat", "tea", "tan", "ate", "nat", "bat"]?

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

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

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

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

Words with the same letters grouped together: "eat", "tea", "ate"; "tan", "nat"; and "bat" alone.

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

Think about how sorting helps identify anagrams.

Describe why sorting each word is important in grouping anagrams.

Focus on how sorting normalizes different words.

Practice

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

easy

A. Count the length of each word and group by length

B. Group words by their first letter only

C. Use sorted strings as keys to group words that are anagrams

D. Use the original word as the key in the hash map

Solution

1. Step 1: Understand anagram grouping

   Anagrams are words with the same letters in different orders. Sorting letters gives a unique key for each group.

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 that are anagrams -> Option C

4. Quick Check:

   Sorted string key = group anagrams [OK]

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

Common Mistakes:

• Grouping by word length only
• Using original word as key without sorting
• Grouping by first letter only

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

easy

A. HashMap map = new HashMap<>();

B. HashMap map = new HashMap<>();

C. Map map = new HashMap<>();

D. Map map = new HashMap<>();

Solution

1. Step 1: Identify correct map types for grouping

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

2. Step 2: Check each option's type correctness

   Map map = new HashMap<>(); uses Map, which is correct. Others have wrong key or value types.

3. Final Answer:

   Map map = new HashMap<>(); -> Option D

4. Quick Check:

   Key=String, Value=List<String> for grouping [OK]

Hint: Use Map for grouping anagrams [OK]

Common Mistakes:

• Using int as key type
• Using String as value instead of List<String>
• Using List<String> as key type

3. What is the output of the following Java code snippet?

String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
Map map = new HashMap<>();
for (String word : words) {
  char[] chars = word.toCharArray();
  Arrays.sort(chars);
  String key = new String(chars);
  map.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
System.out.println(map.values());

medium

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

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

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

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

Solution

1. Step 1: Sort each word to get keys

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

2. Step 2: Group words by sorted keys

   Words with key "aet" grouped: [eat, tea, ate]; key "ant": [tan, nat]; key "abt": [bat].

3. Final Answer:

   [[eat, tea, ate], [tan, nat], [bat]] -> Option A

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

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

Common Mistakes:

• Not sorting words before grouping
• Adding words to wrong groups
• Printing keys instead of grouped values

4. Identify the error in this Java code for grouping anagrams:

String[] words = {"bat", "tab", "eat"};
Map map = new HashMap<>();
for (String word : words) {
  char[] chars = word.toCharArray();
  String key = new String(chars);
  Arrays.sort(chars);
  map.putIfAbsent(key, new ArrayList<>());
  map.get(key).add(word);
}
System.out.println(map.values());

medium

A. Sorting is done after creating the key, so keys are incorrect

B. Using putIfAbsent instead of computeIfAbsent causes error

C. The map should use List<Integer> instead of List<String>

D. The loop should use a while instead of for

Solution

1. Step 1: Check order of sorting and key creation

   Key is created from chars before sorting, so key is unsorted word.

2. Step 2: Identify impact on grouping

   Since keys are unsorted, anagrams get different keys and won't group correctly.

3. Final Answer:

   Sorting is done after creating the key, so keys are incorrect -> Option A

4. Quick Check:

   Sort before key creation to group correctly [OK]

Hint: Sort chars before creating key string [OK]

Common Mistakes:

• Creating key before sorting chars
• Confusing putIfAbsent with computeIfAbsent
• Wrong map value type

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

hard

A. Use the original word as key without any change

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

C. Group words by their length only

D. Sort words but keep original case for keys

Solution

1. Step 1: Understand case-insensitive grouping

   To treat "Eat" and "tea" as same group, ignore case by converting all words to lowercase.

2. Step 2: Apply lowercase conversion before sorting

   Convert word to lowercase, then sort chars to create key. This ensures case differences don't split groups.

3. Step 3: Group words using lowercase sorted keys

   Use these keys in hash map to group anagrams regardless of original case.

4. Final Answer:

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

5. Quick Check:

   Lowercase + sort = case-insensitive grouping [OK]

Hint: Lowercase words before sorting for case-insensitive groups [OK]

Common Mistakes:

• Not converting to lowercase before sorting
• Using original case keys causing split groups
• Grouping by length instead of letters