Anagram Cluster Formation — Problem Statement & Solution Guide

HashingMediumHash Map / Grouping

TimeO(N * L)

SpaceO(N * L)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Hashing and solve the Anagram Cluster Formation problem optimally.

TopicHashing

PatternHash Map / Grouping

TimeO(N * L)

SpaceO(N * L)

Problem Description

Given an array of lowercase alphabetic strings, divide the array into disjoint groups such that every string in a group is an anagram of the others in the same group. Return a collection of these groups; the relative order of groups and the order of strings inside each group are irrelevant. Two strings are anagrams if one can be rearranged to form the other, i.e., they contain exactly the same multiset of characters.

DSA Pattern Breakdown

"Anagram Cluster Formation"

medium

WHY DOES IT MATTER?

Grouping by anagrams is a classic example of reducing a combinatorial equivalence problem to a hashing problem, teaching candidates how to turn a relational property into a constant‑time lookup.

OPTIMIZATION CHALLENGE

The insight is that the order of characters is irrelevant—only the multiset matters—so representing that multiset as a hashable key collapses many comparisons into a single map insertion.

REAL-WORLD CONNECTION

In distributed caching, identical content (e.g., files with the same checksum) is deduplicated by hashing; similarly, anagram grouping deduplicates strings that are permutations of each other.

When coding, first write a helper that returns the canonical key (sorted string or count signature); then the main logic is just a hashmap accumulation—keep the helper pure and test it separately.

COMPLEXITY AT A GLANCE

⏱ Time:O(N * L)

💾 Space:O(N * L)

Core Theory — Why This Approach?

An anagram grouping problem can be reduced to a hashing challenge: each string must be mapped to a canonical representation that is identical for all its anagrams. The most common canonical form is the sorted character sequence, because sorting rearranges any permutation into the same order, yielding O(L log L) per string where L is its length. A more efficient linear‑time alternative is to count the frequency of each of the 26 lowercase letters and encode that count vector as a string or tuple; this yields O(L) per string and avoids the log factor. Naïve pairwise comparison—checking every string against every other—requires O(N^2 * L) time, which quickly becomes infeasible for large N (hundreds of thousands) and long strings. By using a hash map keyed by the canonical form, we can insert each string in amortized O(1) time and collect groups in a single pass, achieving overall linear complexity relative to the total number of characters across all inputs.

Interview Questions on This Problem

Q1How would you group anagrams if the input strings could contain Unicode characters beyond 'a'‑'z'?

Use a frequency map based on a hash map of character→count for each string, then serialize the map (e.g., sorted key‑value pairs) as the hash key; this works for any Unicode set while preserving linear time per string.

Q2What trade‑offs exist between sorting each string versus using a 26‑element count array as the hash key?

Sorting is simpler to implement but costs O(L log L) per string; the count array is O(L) but requires careful serialization to a hashable key and slightly more memory. For short strings the difference is negligible, but for long strings or massive inputs the count method wins.

Q3Can you extend the anagram grouping solution to work in a distributed environment where the dataset is sharded across multiple machines?

Yes—each node computes the canonical key locally and emits (key, string) pairs; a downstream shuffle (like MapReduce’s reduce phase) aggregates by key, producing the final groups without needing cross‑node comparisons.

Examples

Example 1

Input

["listen","silent","enlist","google","gogole","abc","bca","cab","xyz"]

Output

[["listen","silent","enlist"],["google","gogole"],["abc","bca","cab"],["xyz"]]

Explanation: First, sort the characters of each string: "listen"→"eilnst", "silent"→"eilnst", "enlist"→"eilnst" (same key) → group1. "google"→"eggloo", "gogole"→"eggloo" (same key) → group2. "abc","bca","cab" all map to "abc" → group3. "xyz" maps to "xyz" alone → group4. The groups are returned in any order.

Example 2

Input

["rat","tar","art","star","tars","cheese"]

Output

[["rat","tar","art"],["star","tars"],["cheese"]]

Explanation: Sorting each word gives keys: "rat","tar","art" → "art" (group1); "star","tars" → "arst" (group2); "cheese" → "ceeehs" (group3). Each key forms a separate group.

Example 3

Input

["a","b","c","ab","ba","abc","cab","bca","bac"]

Output

[["a"],["b"],["c"],["ab","ba"],["abc","cab","bca","bac"]]

Explanation: Single‑character strings each form their own group because no other string shares the same character. "ab" and "ba" share the sorted key "ab" → group4. All four three‑character strings share the key "abc" → group5. The final list contains five groups in any order.

Constraints

1 <= strs.length <= 100000
1 <= strs[i].length <= 100
strs[i] consists only of lowercase English letters

Optimal Approach & Strategy

Compute a hashable canonical key for each string (sorted letters or frequency vector) and insert the string into a hashmap keyed by that signature, achieving linear time overall.

Brute Force Approach

Compare every pair of strings and check if they are anagrams, placing matching ones together; this requires O(N^2 * L) time.

Code Solutions

Language:

JavaScript Solution

Time: O(N * L)

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(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());
};

const input1 = ["listen", "silent", "enlist", "google", "gogole", "abc", "bca", "cab", "xyz"];
const result1 = groupAnagrams(input1);
console.log("Example 1 Output:", JSON.stringify(result1));

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

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& pair : groups) {
        result.push_back(pair.second);
    }
    
    return result;
}

int main() {
    vector<string> input1 = {"listen", "silent", "enlist", "google", "gogole", "abc", "bca", "cab", "xyz"};
    vector<vector<string>> result1 = groupAnagrams(input1);
    
    cout << "Example 1 Output: [";
    for (const auto& group : result1) {
        cout << "[";
        for (size_t i = 0; i < group.size(); ++i) {
            cout << "\"" << group[i] << "\"";
            if (i < group.size() - 1) cout << ", ";
        }
        cout << "]";
    }
    cout << "]" << endl;
    
    return 0;
}

import java.util.*;

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

    public static void main(String[] args) {
        String[] input1 = {"listen", "silent", "enlist", "google", "gogole", "abc", "bca", "cab", "xyz"};
        List<List<String>> result1 = groupAnagrams(input1);
        
        System.out.println("Example 1 Output: " + result1);
    }
}

from typing import List

def group_anagrams(strs: List[str]) -> List[List[str]]:
    groups = {}
    
    for s in strs:
        key = ''.join(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    
    return list(groups.values())

input1 = ["listen", "silent", "enlist", "google", "gogole", "abc", "bca", "cab", "xyz"]
result1 = group_anagrams(input1)
print("Example 1 Output:", result1)

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(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());
};

const input1 = ["listen", "silent", "enlist", "google", "gogole", "abc", "bca", "cab", "xyz"];
const result1 = groupAnagrams(input1);
console.log("Example 1 Output:", JSON.stringify(result1));

Asked in Top Tech Interviews

FlipkartAdobe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.