Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Examples

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints

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

Thinking Process

  1. Character Frequency as Key: Use character count array to create a unique key for each anagram group
  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

Time Complexity: O(N * K) where N is the number of strings and K is the maximum length of a string
Space Complexity: O(N * K) for storing all strings in the hash map

The key insight is to use a character frequency count as the hash map key. Strings with the same character frequencies are anagrams of each other.

Solution: Character Count Key

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) count[c - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int n : count) key.append('#').append(n);
            groups.computeIfAbsent(key.toString(), x -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}```

### Solution Explanation

**Approach:** Two pointers on string (this problem)

**Key idea:** 1. **Character Frequency as Key**: Use character count array to create a unique key for each anagram group

**How the code works:**
1. **Character Frequency as Key**: Use character count array to create a unique key for each anagram group
- Strings often need frequency maps or two-pointer scans.
- Watch index bounds and empty-string edge cases.
- Stack helps with nested or repeated patterns.

**Walkthrough** — input `strs = ["eat","tea","tan","ate","nat","bat"]`, expected output `[["bat"],["nat","tan"],["ate","eat","tea"]]`:

1. Initialize variables from the problem setup.
2. Apply the main loop / recursion until the condition is met.
3. Confirm the result matches the expected output.

| Approach | Time | Space | Pros | Cons |
|----------|------|-------|------|------|
| **Character Count Key** | O(N * K) | O(N * K) | Fast, no sorting | String concatenation overhead |
| **Sorted String Key** | O(N * K log K) | O(N * K) | Simple, readable | Slower due to sorting |
| **Prime Number Hash** | O(N * K) | O(N * K) | Very fast key generation | Overflow risk, complex |
## Algorithm Breakdown

```java
// import java.util.Arrays;
// import java.util.Collections;
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap<>();

        for(String s: strs) {
            String key = s;
            Arrays.sort(key);
            hm.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        List<List<String>> rtn = new ArrayList<>();
        for (var e : hm.entrySet()) {
            rtn.add(group);
        }

        return rtn;
    }
}

Complexity

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Character Count Key | O(N * K) | O(N * K) | Fast, no sorting | String concatenation overhead | | Sorted String Key | O(N * K log K) | O(N * K) | Simple, readable | Slower due to sorting | | Prime Number Hash | O(N * K) | O(N * K) | Very fast key generation | Overflow risk, complex |

Why Character Count Key is Preferred

  1. Optimal Time Complexity: O(N * K) without sorting overhead
  2. Predictable Performance: No dependency on string length for key generation
  3. Memory Efficient: Fixed-size count array (26 integers)
  4. Robust: Works for any string length without overflow concerns

Implementation Details

Character Count Array

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) count[c - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int n : count) key.append('#').append(n);
            groups.computeIfAbsent(key.toString(), x -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}```

### Key Construction

```cpp
string key = "";
for(int i = 0; i < 26; i++) {
    key += "#";              // Delimiter prevents ambiguity
    key += to_string(count[i]);  // Count for letter at position i
}

Why use “#” delimiter?

  • Without delimiter: “12” could mean count[0]=1, count[1]=2 OR count[0]=12
  • With delimiter: “#1#2” unambiguously means count[0]=1, count[1]=2

Java20 contains() Method

if(!hm.contains(key)) hm[key] = vector<string>();

Alternative (Java11/14):

if(hm.find(key) == hm.end()) hm[key] = vector<string>();

Common Mistakes

  1. Empty input: strs = [] → return []
  2. Single empty string: strs = [""] → return [[""]]
  3. Single character: strs = ["a"] → return [["a"]]
  4. All anagrams: strs = ["eat","tea","ate"] → return [["eat","tea","ate"]]

  5. No anagrams: strs = ["abc","def","ghi"] → return [["abc"],["def"],["ghi"]]

  6. Forgetting to reset count array: Must reset for each string
  7. Wrong delimiter: Using numbers without delimiter causes key collisions
  8. Case sensitivity: Assuming uppercase letters (this problem uses lowercase only)
  9. Empty string handling: Not handling empty input or empty strings correctly
  10. Inefficient key generation: Using sorting when counting is faster

Optimization Tips

  1. Pre-allocate result vector: Can reserve space if you know approximate number of groups
  2. Use emplace_back: More efficient than push_back for strings
  3. Avoid string concatenation: Character count approach minimizes this overhead
  4. Early return: Handle empty input immediately

Real-World Applications

  1. Word Games: Grouping words by anagram patterns (Scrabble, Boggle)
  2. Text Analysis: Finding similar words or patterns in text
  3. Cryptography: Anagram-based ciphers and puzzles
  4. Search Engines: Grouping similar search terms
  5. Data Deduplication: Identifying similar strings

Key Takeaways

  1. Character Frequency as Key: Use character count array to create a unique key for each anagram group
  2. Hash Map Grouping: Strings with identical character frequencies map to the same key
  3. Delimiter Usage: Using “#” delimiter ensures keys are unique (e.g., “1#2” vs “12#”)
  4. Efficient Counting: Count array of size 26 (for lowercase letters) is space-efficient

References

Template Reference