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:
    def groupAnagrams(self, strs):
        if len(strs) == 0:
            return []

        hm = {}

        for s in strs:
            count = [0] * 26

            for c in s:
                count[ord(c) - ord('a')] += 1

            key = ""
            for i in range(26):
                key += "#"
                key += str(count[i])

            if key not in hm:
                hm[key] = []

            hm[key].append(s)

        rtn = []

        for key in hm:
            rtn.append(hm[key])

        return rtn

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

def group_anagrams(strs: list[str]) -> list[list[str]]:
    if not strs:
        return []
    hm: dict[str, list[str]] = {}
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord("a")] += 1
        key = "".join(f"#{n}" for n in count)
        hm.setdefault(key, []).append(s)
    return list(hm.values())

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:
    def groupAnagrams(self, strs):
        hm = {}

        for s in strs:
            key = ''.join(sorted(s))
            if key not in hm:
                hm[key] = []
            hm[key].append(s)

        rtn = []

        for key in hm:
            rtn.append(hm[key])

        return rtn

Key Construction

class Solution:
    def groupAnagrams(self, strs):
        # Prime numbers for each letter
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
                  59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

        hm = {}

        for s in strs:
            key = 1

            for c in s:
                key *= primes[ord(c) - ord('a')]

            if key not in hm:
                hm[key] = []

            hm[key].append(s)

        rtn = []

        for key in hm:
            rtn.append(hm[key])

        return rtn

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

Python20 contains() Method

count = [0] * 26
for c in s:
    count[ord(c) - ord("a")] += 1

Alternative (Python11/14):

key = "".join(f"#{n}" for n in count)

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