medium Group Anagrams

Problem Statement

Given a list of strings, the task is to group the anagrams together.

An anagram is a word or phrase formed by rearranging the letters of another, such as "cinema", formed from "iceman"

You can return the answer in any order.

Examples

Example 1:

• Input: ["dog", "god", "hello"]
• Output: [["dog", "god"], ["hello"]]
• Justification: "dog" and "god" are anagrams, so they are grouped together. "hello" does not have any anagrams in the list, so it is in its own group.

Example 2:

• Input: ["listen", "silent", "enlist"]
• Output: [["listen", "silent", "enlist"]]
• Justification: All three words are anagrams of each other, so they are grouped together.

Example 3:

• Input: ["abc", "cab", "bca", "xyz", "zxy"]
• Output: [["abc", "cab", "bca"], ["xyz", "zxy"]]
• Justification: "abc", "cab", and "bca" are anagrams, as are "xyz" and "zxy".

Constraints:

• 1 <= strs.length <= 10⁴
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Solution

• Sorting Approach:

  • For each word in the input list:
    • Sort the letters of the word.
    • Use the sorted word as a key in a hash map, and add the original word to the list of values for that key.
  • The hash map values will be the groups of anagrams.

• Why This Will Work:

  • Anagrams will always result in the same sorted word, so they will be grouped together in the hash map.

Algorithm Walkthrough

• Given the input ["abc", "cab", "bca", "xyz", "zxy"]
• For "abc":
  • Sorted word is "abc".
  • Add "abc" to the hash map with key "abc".
• For "cab":
  • Sorted word is "abc".
  • Add "cab" to the list in the hash map with key "abc".
• Continue this process for all words.
• The hash map values are the groups of anagrams.

Code

import java.util.*;

public class Solution {

  public List<List<String>> groupAnagrams(String[] strs) {
    // Map to hold sorted word as key and list of words as value
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
      char[] characters = str.toCharArray();
      Arrays.sort(characters);
      String sorted = new String(characters);
      // If the sorted word is not already a key in the map, add it with a new list as its value
      if (!map.containsKey(sorted)) {
        map.put(sorted, new ArrayList<>());
      }
      // Add the original word to the list of values for the sorted word key
      map.get(sorted).add(str);
    }
    // Return the values of the map as a list of lists
    return new ArrayList<>(map.values());
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(
      sol.groupAnagrams(new String[] { "dog", "god", "hello" })
    );
    System.out.println(
      sol.groupAnagrams(new String[] { "listen", "silent", "enlist" })
    );
    System.out.println(
      sol.groupAnagrams(new String[] { "abc", "cab", "bca", "xyz", "zxy" })
    );
  }
}

Complexity Analysis

• Time Complexity: , where n is the number of strings, and k is the maximum length of a string in strs. This is because each of the n strings is sorted in time.
• Space Complexity: , where n is the number of strings, and k is the maximum length of a string in strs. This space is used for the output data structure and the hash map.

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Group Anagrams

Why this concept exists (judgment layer)

Solution sorts each word as map key — correct and clear. Elevation derives O(n k log k), shows count-signature alternative, and when-NOT pairwise anagram checks O(n² k).

Worked example with complexity derivation

["abc","cab","bca","xyz","zxy"]:
key "abc"→[abc,cab,bca]; "xyz"→[xyz,zxy].
Each sort k log k, n words → O(n k log k); map space O(n k).
Pairwise: for each pair sort-compare → O(n² k log k) death at n=1e4.

Pattern + when-NOT / named alternative

PATTERN: Map<signature, List<word>>. WHEN NOT: only check anagram pair → no group map. Unicode → HashMap counts. If order of groups/words required specific — problem allows any order.

Edge case / failure mode

Edges: strs=[""] → [[""]]; all unique keys; duplicate inputs appear multiple times in list. Hand-run dog/god/hello → two groups.

Hostile-panel drills (defend the decision)

Q1. Derive time complexity from the code.
Model answer: for each of n strings: sort O(k log k) + O(1) avg map → O(n k log k).

Q2. Count-key encoding sketch?
Model answer: int[26] → string like #1#0#2… as key; build O(k).

Q3. Why not Trie of sorted words?
Model answer: Works but heavier; hash map is standard interview answer.