Definition
- Group Anagrams – partition a list of strings into groups where each group contains mutual anagrams.
- Canonical key – sort each word's characters to produce a fingerprint that is the same for every member of an anagram family.
- HashMap bucketing – map from the sorted key to a list of original strings using
computeIfAbsent. - Count-signature alternative – build a key from the 26 letter frequencies, which is O(k) per word instead of O(k log k).
- Complexity – O(n * k log k) with sorted keys or O(n * k) with count-signature keys.
National Bank of India has a pile of transaction tag strings and wants to bucket together all tags that are shuffles of each other. Rajesh gives every tag a fingerprint by sorting its letters, so "debit" and "bited" both become "bdeit". Tags with the same fingerprint go into the same bucket.
Understanding the Concepts
What is the Group Anagrams problem?
Given a list of strings, group them so that all anagrams are in the same group. Two strings are anagrams if one is a rearrangement of the other. For example, ["eat","tea","tan","ate","nat","bat"] groups into [["eat","tea","ate"],["tan","nat"],["bat"]].
package com.bank.core;
import java.util.*;
public class GroupAnagrams {
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);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
System.out.println(groupAnagrams(input));
}
}
[[eat, tea, ate], [bat], [tan, nat]]
How does the sorted-key approach work?
The core idea is a canonical form. Two strings are anagrams exactly when their sorted character sequences are identical. You convert each string to a char array, sort it, and build a String from the sorted array. This sorted string is the canonical key that is the same for every anagram and different for non-anagrams.
You use this key to bucket strings into a HashMap. The computeIfAbsent method creates an empty list if the key is new, and you add the original string to the list.
package com.bank.core;
import java.util.*;
public class SortedKeyExplained {
public static void main(String[] args) {
String[] words = {"debit", "bited", "credit"};
for (String w : words) {
char[] c = w.toCharArray();
Arrays.sort(c);
System.out.println(w + " -> key: " + new String(c));
}
}
}
debit -> key: bdeit
bited -> key: bdeit
credit -> key: cdeirt
What is the count-signature alternative?
Instead of sorting, build a key string from the 26 letter frequencies. For each word, count how many of each letter it has and join the counts with a separator. This key is O(k) to build instead of O(k log k) for sorting, which is faster for long words over a small alphabet.
package com.bank.core;
import java.util.*;
public class CountSignatureKey {
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder keyBuilder = new StringBuilder();
for (int i = 0; i < 26; i++) {
keyBuilder.append(count[i]).append('#');
}
String key = keyBuilder.toString();
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
System.out.println(groupAnagrams(input));
}
}
[[eat, tea, ate], [bat], [tan, nat]]
How do the two keying strategies compare?
| Feature | Sorted key | Count-signature key |
|---|---|---|
| Time per word | O(k log k) | O(k) |
| Key length | k characters | Up to 26 counts + separators |
| Collision-free | Yes | Yes |
| Simplicity | Very simple | Slightly more code |
| Best for | Short words, simplicity | Long words, small alphabet |
Both are collision-free canonical forms, meaning two different anagram families never share a key. This is essential for correctness.
Why is a weak key like char-code sum wrong?
A tempting shortcut is to sum the character codes as a key. This is not collision-free: different letter sets can produce the same sum. For example, "ad" (97+100=197) and "bc" (98+99=197) have the same sum but are not anagrams.
package com.bank.core;
public class WeakKeyBug {
public static void main(String[] args) {
// Same sum, not anagrams
String a = "ad", b = "bc";
int sumA = a.chars().sum();
int sumB = b.chars().sum();
System.out.println("Sum of 'ad': " + sumA);
System.out.println("Sum of 'bc': " + sumB);
System.out.println("Same sum: " + (sumA == sumB)); // true, but NOT anagrams
}
}
Sum of 'ad': 197
Sum of 'bc': 197
Same sum: true
What about case-insensitive grouping?
If grouping should ignore case, lowercase each string before computing the key. If spaces and punctuation should be ignored, strip them first.
package com.bank.service;
import java.util.*;
public class CaseInsensitiveGrouping {
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toLowerCase().toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
String[] tags = {"Debit", "BITED", "Credit"};
System.out.println(groupAnagrams(tags));
}
}
[[Debit, BITED], [Credit]]
What are the edge cases?
Edge cases include empty strings (all empty strings are anagrams of each other), single-character strings, a list with one element, and strings of all identical characters.
package com.bank.core;
import java.util.*;
public class GroupAnagramsEdgeCases {
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] c = s.toCharArray(); Arrays.sort(c);
map.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
System.out.println("Empty strings: " + groupAnagrams(new String[]{"", ""}));
System.out.println("Single: " + groupAnagrams(new String[]{"a"}));
System.out.println("All same: " + groupAnagrams(new String[]{"aaa", "aaa"}));
}
}
Empty strings: [[, ]]
Single: [[a]]
All same: [[aaa, aaa]]
What is the time and space complexity?
With sorted keys, each word of length k costs O(k log k) to sort. For n words with average length k, the total is O(n * k log k). With count-signature keys, each word costs O(k), giving O(n * k) total. Space is O(n * k) for storing all strings in the map.
What is the banking use case?
At National Bank of India, Rajesh groups free-form transaction tags into anagram families so Priya can examine one canonical family instead of many shuffled variants. The system uses case-insensitive keying and a LinkedHashMap for a stable, first-seen group order in the review report.
package com.bank.service;
import java.util.*;
public class TransactionTagGrouper {
public static Map<String, List<String>> groupTags(String[] tags) {
Map<String, List<String>> groups = new LinkedHashMap<>();
for (String tag : tags) {
char[] c = tag.toLowerCase().toCharArray();
Arrays.sort(c);
groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(tag);
}
return groups;
}
public static void main(String[] args) {
String[] tags = {"Transfer", "Deposit", "Reftsanr", "Deposti"};
Map<String, List<String>> grouped = groupTags(tags);
grouped.forEach((key, group) -> System.out.println("Group: " + group));
}
}
Group: [Transfer, Reftsanr]
Group: [Deposit, Deposti]
Visual Overview
Group Anagrams: Sorted Key Bucketing ═════════════════════════════════════ Input: ["eat", "tea", "tan", "ate", "nat", "bat"] Compute sorted key for each word: "eat" → "aet" "tea" → "aet" "tan" → "ant" "ate" → "aet" "nat" → "ant" "bat" → "abt" HashMap bucketing: ┌────────┬─────────────────┐ │ Key │ Group │ ├────────┼─────────────────┤ │ "aet" │ [eat, tea, ate] │ │ "ant" │ [tan, nat] │ │ "abt" │ [bat] │ └────────┴─────────────────┘ Output: [[eat, tea, ate], [tan, nat], [bat]]
Key Takeaway
Group Anagrams partitions a list of strings into families where each family contains mutual anagrams. The solution computes a canonical key for each string: sort its characters to produce a fingerprint that is the same for every anagram. Use this fingerprint as a HashMap key to bucket strings into groups.
The sorted key costs O(k log k) per word. The count-signature alternative builds a key from the 26 letter frequencies at O(k) per word, which is faster for long words. Both keys are collision-free, meaning different anagram families never share a key. A weak key like summing character codes is not collision-free and would wrongly merge non-anagrams.
Normalise by lowercasing when case-insensitive grouping is needed, and use a LinkedHashMap when a stable, first-seen group order is required.
In the banking project at National Bank of India, Rajesh groups free-form transaction tags into anagram families so Priya can review one canonical family instead of many shuffled variants, with case-insensitive keying and stable report order.
Remember one sentence: sort each word's letters as a canonical key, bucket into a HashMap, and all anagrams land in the same group in O(n * k log k) time.
---