Group Anagrams Together — Problem Statement & Solution Guide
Problem Description
You are provided with an array of lowercase alphabetic strings. Two strings are considered anagrams if one can be formed by rearranging the characters of the other. Your task is to partition the input array into groups such that all strings within a single group are anagrams of each other, and no string belongs to more than one group.
Return a list of lists where each inner list contains the original strings that form a valid anagram group. The order of the groups in the final output does not matter, nor does the order of strings within each group.
For example, if the input contains "eat", "tea", and "ate", these three strings must appear in the same group because they share the exact same character frequency profile. Conversely, "ant" and "tan" would form a separate group if present.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Group Anagrams Together"
WHY DOES IT MATTER?
This pattern is essential for any problem involving grouping items based on a property that is invariant under permutation or transformation. It teaches the power of canonical representation and hashing to reduce complex comparison problems to simple lookup problems, a core skill for optimizing algorithms in data-intensive applications.
OPTIMIZATION CHALLENGE
The key insight is to avoid pairwise comparisons. Instead of asking 'Is string A an anagram of string B?', we ask 'What is the canonical form of string A?' and 'What is the canonical form of string B?'. If the canonical forms match, they are anagrams. This shifts the computational burden from O(N^2) comparisons to O(N) key generations and hash lookups.
REAL-WORLD CONNECTION
In distributed systems, this is analogous to data sharding or partitioning. Just as anagrams are grouped by their sorted character signature, data points in a distributed database are often sharded by a hash of their key. This ensures that related data (anagrams) ends up in the same partition (group), enabling efficient local processing and reducing cross-node communication.
During the interview, explicitly mention the trade-off between sorting (O(K log K)) and frequency counting (O(K)) for key generation. If the alphabet is small (like 26 letters), frequency counting is often faster in practice due to lower constant factors and no need for sorting logic. Also, emphasize that the original strings must be preserved in the output, not just the keys.
COMPLEXITY AT A GLANCE
O(N * K log K)O(N * K)Core Theory — Why This Approach?
The problem of grouping anagrams relies on the mathematical property that anagrams share an identical multiset of characters. The naive approach involves checking every pair of strings to determine if they are anagrams, which requires sorting each string multiple times or counting character frequencies for every comparison, resulting in a time complexity of O(N^2 * K log K), where N is the number of strings and K is the maximum string length. This quadratic behavior becomes prohibitive for large datasets, as the cost of verifying relationships scales poorly with input size.
The optimal paradigm utilizes hashing to create a canonical representation for each anagram group. By sorting the characters of each string (or using a fixed-size frequency array as a key), we generate a unique identifier that remains invariant for all anagrams of that group. This transforms the problem from a pairwise comparison task into a single-pass grouping task. We iterate through the input array exactly once, compute the canonical key for each string, and append the original string to a list associated with that key in a hash map.
This approach reduces the time complexity to O(N * K log K) due to the sorting operation for each string, or O(N * K) if using a frequency array as the key (since the alphabet size is constant at 26). The space complexity is O(N * K) to store the groups. This shift from O(N^2) comparisons to O(N) hash lookups is the fundamental algorithmic insight that makes the solution scalable for production-grade data volumes.
Interview Questions on This Problem
Q1At a fintech platform processing millions of transaction descriptions, how would you modify the anagram grouping algorithm to handle case-insensitive grouping and ignore non-alphabetic characters?
Normalize the input strings before generating the key. Convert all characters to lowercase and filter out non-alphabetic characters (e.g., using a regex or a simple loop checking isalpha()). Then, apply the standard sorting or frequency-counting logic to the normalized string. This ensures that 'Abc!' and 'bca' are grouped together. The time complexity remains O(N * K log K) or O(N * K) depending on the key generation method, with a slight constant factor increase for normalization.
Q2In a high-growth startup with limited memory, how would you optimize the space complexity if the input strings are very long (K is large) but the number of unique anagram groups is small?
Instead of storing the full sorted string as the key, use a frequency array of size 26 (for lowercase English letters) as the key. Convert this array into a string or a tuple to make it hashable. This reduces the key size from O(K) to O(26), which is constant. However, you still need to store the original strings in the groups. If memory is still a concern, consider external sorting or processing the data in chunks if it doesn't fit in RAM, but for in-memory optimization, the frequency array key is the most efficient way to reduce the overhead of the hash map keys.
Q3How would you extend this solution to group strings that are anagrams of each other but allow for one character substitution (i.e., 'edit distance' of 1)?
This becomes a more complex problem. One approach is to generate all possible 'neighbor' strings by replacing each character with every other letter and checking if the neighbor exists in the hash map. However, this is inefficient. A better approach for 'one substitution' is to use a trie or a modified hash map where the key is the string with one character removed (for deletions) or a specific pattern. For substitutions, you might need to check all possible single-character changes, which is O(26 * K) per string. This is significantly more complex and may require a different data structure like a Trie to efficiently find near-matches.
Examples
Input
strs = ["cab", "abc", "bca", "xyz", "zyx"]
Output
[["cab", "abc", "bca"], ["xyz", "zyx"]]
Explanation: 1. Process "cab": Character frequencies are {a:1, b:1, c:1}. Create a new group with key "abc" (sorted string) and add "cab". 2. Process "abc": Character frequencies are {a:1, b:1, c:1}. Sorted key is "abc". This key exists, so add "abc" to the existing group. 3. Process "bca": Character frequencies are {a:1, b:1, c:1}. Sorted key is "abc". Add "bca" to the existing group. 4. Process "xyz": Character frequencies are {x:1, y:1, z:1}. Sorted key is "xyz". Create a new group and add "xyz". 5. Process "zyx": Character frequencies are {x:1, y:1, z:1}. Sorted key is "xyz". Add "zyx" to the existing group. Final groups: [["cab", "abc", "bca"], ["xyz", "zyx"]].
Input
strs = ["listen", "silent", "enlist", "hello", "olleh"]
Output
[["listen", "silent", "enlist"], ["hello", "olleh"]]
Explanation: 1. "listen" sorts to "eilnst". Group 1 created. 2. "silent" sorts to "eilnst". Added to Group 1. 3. "enlist" sorts to "eilnst". Added to Group 1. 4. "hello" sorts to "ehllo". Group 2 created. 5. "olleh" sorts to "ehllo". Added to Group 2. Final groups: [["listen", "silent", "enlist"], ["hello", "olleh"]].
Input
strs = ["a", "b", "a", "c", "b"]
Output
[["a", "a"], ["b", "b"], ["c"]]
Explanation: 1. "a" sorts to "a". Group 1 created. 2. "b" sorts to "b". Group 2 created. 3. "a" sorts to "a". Added to Group 1. 4. "c" sorts to "c". Group 3 created. 5. "b" sorts to "b". Added to Group 2. Final groups: [["a", "a"], ["b", "b"], ["c"]].
Constraints
- 1 <= strs.length <= 10^4
- 1 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters only.
Optimal Approach & Strategy
Generate a canonical key for each string by sorting its characters or using a frequency array. Use a hash map to group strings by their key in a single pass. This reduces the time complexity to O(N * K log K) or O(N * K) and space to O(N * K).
Brute Force Approach
Compare every pair of strings in the array to check if they are anagrams by sorting both and comparing, or by counting character frequencies for each pair. This results in O(N^2 * K log K) time complexity, which is too slow for large inputs.
Verified Code Solutions
function groupAnagrams(strs) {
const map = new Map();
for(const s of strs){
const key = s.split('').sort().join('');
if(!map.has(key)) map.set(key, []);
map.get(key).push(s);
}
const groups = [];
for(const arr of map.values()){
arr.sort(); // deterministic order
groups.push(arr);
}
groups.sort((a,b)=> a[0].localeCompare(b[0]));
return groups;
}
// Driver (same as template)
function main(){
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
if(input.length===0) return;
const n = parseInt(input[0],10);
const strs = input.slice(1,1+n);
const groups = groupAnagrams(strs);
groups.forEach(g=> console.log(g.join(' ')));
}
main();#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> groupAnagrams(const vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for(const string& s : strs){
string key = s;
sort(key.begin(), key.end());
mp[key].push_back(s);
}
vector<vector<string>> res;
for(auto &p : mp){
auto &group = p.second;
sort(group.begin(), group.end()); // optional: deterministic order
res.push_back(group);
}
// sort groups by first element for deterministic output
sort(res.begin(), res.end(), [](const vector<string>& a, const vector<string>& b){
return a[0] < b[0];
});
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<string> strs(n);
for(int i=0;i<n;++i) cin>>strs[i];
auto groups = groupAnagrams(strs);
for(const auto& g: groups){
for(const auto& s: g) cout<<s<<' ';
cout<<'\n';
}
return 0;
}import java.util.*;
public class Main {
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String s : strs){
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
List<List<String>> res = new ArrayList<>();
for(List<String> group : map.values()){
Collections.sort(group);
res.add(group);
}
res.sort(Comparator.comparing(list -> list.get(0)));
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] strs = new String[n];
for(int i=0;i<n;i++) strs[i] = sc.next();
List<List<String>> groups = groupAnagrams(strs);
for(List<String> g : groups){
for(String s : g) System.out.print(s + " ");
System.out.println();
}
sc.close();
}
}from typing import List
from collections import defaultdict
def group_anagrams(strs: List[str]) -> List[List[str]]:
mp = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
mp[key].append(s)
groups = []
for group in mp.values():
group.sort()
groups.append(group)
groups.sort(key=lambda g: g[0])
return groups
def main():
import sys
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
strs = data[1:1+n]
groups = group_anagrams(strs)
for g in groups:
print(' '.join(g))
if __name__ == "__main__":
main()function groupAnagrams(strs) {
const map = new Map();
for(const s of strs){
const key = s.split('').sort().join('');
if(!map.has(key)) map.set(key, []);
map.get(key).push(s);
}
const groups = [];
for(const arr of map.values()){
arr.sort(); // deterministic order
groups.push(arr);
}
groups.sort((a,b)=> a[0].localeCompare(b[0]));
return groups;
}
// Driver (same as template)
function main(){
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
if(input.length===0) return;
const n = parseInt(input[0],10);
const strs = input.slice(1,1+n);
const groups = groupAnagrams(strs);
groups.forEach(g=> console.log(g.join(' ')));
}
main();Asked in Top Tech Interviews
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.