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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Grouping Anagrams by Sorted Key

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

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> 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());
    }
}

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

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

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

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

💡 Hint

Think about how sorting each word groups anagrams under the same key.

The code sorts each word to create a key. Anagrams have the same sorted key, so they group together. The output is a collection of lists where each list contains anagrams.

🧠 Conceptual

intermediate

Why Use Sorted Strings as Keys in Grouping Anagrams?

Why is sorting each string used as the key in a hash map when grouping anagrams?

A Because sorted strings reduce memory usage in the hash map.

B Because sorting strings makes the hash map faster to access.

C Because sorted strings of anagrams are identical, allowing grouping by the same key.

D Because sorting strings removes duplicate characters.

💡 Hint

Think about what makes anagrams similar when rearranged.

Anagrams have the same letters in different orders. Sorting letters puts them in the same order, so anagrams share the same sorted string key.

🔧 Debug

advanced

Identify the Error in Grouping Anagrams Code

What error will the following Java code produce when grouping anagrams using a hash map?

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String[] words = {"bat", "tab", "eat"};
        Map<String, List<String>> 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());
    }
}

A The map groups incorrectly because the key is created before sorting, so anagrams have different keys.

B The map groups anagrams correctly: [[bat, tab], [eat]]

C The code throws a NullPointerException at map.get(key).add(word).

D The code throws a compile-time error due to incorrect use of Arrays.sort.

💡 Hint

Check the order of sorting and key creation.

The key is created before sorting the char array, so keys are different for anagrams. This causes incorrect grouping.

❓ Predict Output

advanced

Output of Group Anagrams Using Character Count as Key

What is the output of the following Java code that groups anagrams using character count arrays as keys?

DSA Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String[] words = {"abc", "bca", "cab", "xyz", "zyx"};
        Map<String, List<String>> map = new HashMap<>();
        for (String word : words) {
            int[] count = new int[26];
            for (char c : word.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder keyBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                keyBuilder.append('#').append(count[i]);
            }
            String key = keyBuilder.toString();
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }
        System.out.println(map.values());
    }
}

A [[abc], [bca], [cab], [xyz], [zyx]]

B [[abc, bca, cab], [xyz, zyx]]

C [[abc, bca], [cab, xyz, zyx]]

D [[abc, bca, cab, xyz, zyx]]

💡 Hint

Character count arrays uniquely identify anagrams.

The code counts characters for each word and uses the counts as a key. Anagrams have identical counts, so they group together.

🧠 Conceptual

expert

Why Use Character Count Instead of Sorting for Grouping Anagrams?

What is the main advantage of using character count arrays as keys instead of sorting strings when grouping anagrams?

A Character count arrays use less memory than sorted strings.

B Character count arrays simplify the code by avoiding loops.

C Character count arrays allow grouping of non-anagram words as well.

D Character count arrays provide a faster O(n) key generation compared to O(n log n) sorting.

💡 Hint

Consider the time complexity of sorting vs counting characters.

Counting characters takes linear time relative to word length, while sorting takes more time. This makes character count keys faster for large inputs.

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