Group Anagrams

Problem Statement

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.

What to notice first

Anagrams share the same character frequency — and therefore the same sorted form. Both observations lead directly to an O(1)-comparison group key.

Examples

Input	Output
["eat","tea","tan","ate","nat","bat"]	[["bat"],["nat","tan"],["ate","eat","tea"]]
[""]	[[""]]
["a"]	[["a"]]

Constraints

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

Real-World Applications

Where this pattern appears

• Log file clustering — group log messages by their normalised template.
• Search query deduplication — recognise that “listen” and “silent” are the same search intent.
• Spell checker — find all valid rearrangements of a misspelled word.
• DNA sequence grouping — cluster gene sequences that are permutations of each other.

Complexity Comparison

Approach	Time	Space	Best When
Sort Key	O(n·k·log k)	O(n·k)	General case, simple to implement
Char Count	O(n·k)	O(n·k)	Long strings where sort cost is noticeable

Approach 1: Sort Key (Recommended)

★ Recommended

Sort each string’s characters to produce a canonical key. Words that are anagrams will produce the same key and get appended to the same bucket in the hash map.

⏱ Time O(n·k·log k) k = max string length; sorting each string costs k log k 💾 Space O(n·k) All strings stored once in the map

Step-by-step Example

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

Word	Sorted key	Groups state
"eat"	"aet"	{"aet": ["eat"]}
"tea"	"aet"	{"aet": ["eat","tea"]}
"tan"	"ant"	{"aet": ["eat","tea"], "ant": ["tan"]}
"ate"	"aet"	{"aet": ["eat","tea","ate"], "ant": ["tan"]}
"nat"	"ant"	{..., "ant": ["tan","nat"]}
"bat"	"abt"	{..., "abt": ["bat"]}

Animated walkthrough

How sort key groups anagrams

Use Next or Autoplay to watch each word get sorted into its canonical key, then placed into the correct bucket.

Back Autoplay Next Reset

Step 1 of 6

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = sorted(s) as tuple/string
        groups[key].append(s)
    return list(groups.values())

Solution Code

Python

group_anagrams_sort_key.py

from typing import List
from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

print(groupAnagrams(["eat","tea","tan","ate","nat","bat"]))

C++

group_anagrams_sort_key.cpp

#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (const string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            groups[key].push_back(s);
        }
        vector<vector<string>> result;
        for (auto& [k, v] : groups) {
            result.push_back(v);
        }
        return result;
    }
};

Java

group_anagrams_sort_key.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

JavaScript

group_anagrams_sort_key.js

function groupAnagrams(strs) {
    const groups = new Map();
    for (const s of strs) {
        const key = s.split('').sort().join('');
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(s);
    }
    return Array.from(groups.values());
}

console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));

Rust

group_anagrams_sort_key.rs

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut groups: HashMap<Vec<char>, Vec<String>> = HashMap::new();
        for s in strs {
            let mut key: Vec<char> = s.chars().collect();
            key.sort_unstable();
            groups.entry(key).or_default().push(s);
        }
        groups.into_values().collect()
    }
}

Go

group_anagrams_sort_key.go

import "sort"

func groupAnagrams(strs []string) [][]string {
  groups := map[string][]string{}
  for _, s := range strs {
    runes := []rune(s)
    sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
    key := string(runes)
    groups[key] = append(groups[key], s)
  }
  result := make([][]string, 0, len(groups))
  for _, v := range groups {
    result = append(result, v)
  }
  return result
}

Approach 2: Character Count

🎯 Interview Favourite

Instead of sorting, count the frequency of each of the 26 lowercase letters and use that count array as the key. This removes the log k sort factor, giving a linear-per-string cost.

⏱ Time O(n·k) k = max string length; one pass per string 💾 Space O(n·k) All strings stored once in the map

How the Key Works

For "eat":

• count[4] (e) = 1, count[0] (a) = 1, count[19] (t) = 1
• key = (0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0)

For "tea" — identical count array → same bucket as "eat".

Pseudocode

function groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

Solution Code

Python

group_anagrams_char_count.py

from typing import List
from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

print(groupAnagrams(["eat","tea","tan","ate","nat","bat"]))

C++

group_anagrams_char_count.cpp

#include <array>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        auto encode = [](const string& s) {
            array<int, 26> count{};
            for (char c : s) count[c - 'a']++;
            string key;
            for (int n : count) key += to_string(n) + ',';
            return key;
        };
        unordered_map<string, vector<string>> groups;
        for (const string& s : strs) {
            groups[encode(s)].push_back(s);
        }
        vector<vector<string>> result;
        for (auto& [k, v] : groups) {
            result.push_back(v);
        }
        return result;
    }
};

Java

group_anagrams_char_count.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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']++;
            String key = Arrays.toString(count);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

JavaScript

group_anagrams_char_count.js

function groupAnagrams(strs) {
    const groups = new Map();
    for (const s of strs) {
        const count = new Array(26).fill(0);
        for (const c of s) count[c.charCodeAt(0) - 97]++;
        const key = count.join(',');
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(s);
    }
    return Array.from(groups.values());
}

console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));

Rust

group_anagrams_char_count.rs

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut groups: HashMap<[u32; 26], Vec<String>> = HashMap::new();
        for s in strs {
            let mut count = [0u32; 26];
            for c in s.chars() {
                count[(c as u8 - b'a') as usize] += 1;
            }
            groups.entry(count).or_default().push(s);
        }
        groups.into_values().collect()
    }
}

Go

group_anagrams_char_count.go

import "fmt"

func groupAnagrams(strs []string) [][]string {
  groups := map[[26]int][]string{}
  for _, s := range strs {
    var count [26]int
    for _, c := range s {
      count[c-'a']++
    }
    groups[count] = append(groups[count], s)
  }
  result := make([][]string, 0, len(groups))
  for _, v := range groups {
    result = append(result, v)
  }
  return result
}

func main() {
  fmt.Println(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
}

Watch for these pitfalls

• Using the string itself as a key instead of its sorted/counted form — “eat” and “tea” would be treated as different groups.
• Forgetting that the empty string "" is a valid input — its sorted form is also "" and its count array is all zeros; it forms its own group.
• In Java, using Arrays.sort() on a char[] and then new String(arr) as the key is correct — do not sort the original string variable directly.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

group_anagrams_space_optimized.py

"""
Solution for Group Anagrams
"""

def solve():
    """Implementation for approach 3 of Group Anagrams"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

group_anagrams_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Group Anagrams
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

GroupAnagramsSpaceOptimized.java

/**
 * Solution for Group Anagrams
 * Approach 3
 */
public class GroupAnagramsSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

group_anagrams_space_optimized.js

/**
 * Solution for Group Anagrams
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

group_anagrams_space_optimized.rs

/// Solution for Group Anagrams
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

group_anagrams_space_optimized.go

package main

import "fmt"

// Solution for Group Anagrams
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum ↗ Easy #1
• Valid Anagram ↗ Easy #242
• Top K Frequent Elements ↗ Medium #347

Interview Tips

Key trade-offs to discuss

• The sort key approach is the clearest to explain in an interview. Lead with it.
• Mention the char count optimisation as a follow-up: it removes the log k factor for long strings.
• Edge cases: empty string (valid group of its own), single character strings, all strings identical.

← Previous
#46 Permutations Next
#50 Pow(x, n) →