Problem overview
An anagram of a word uses exactly the same letters, rearranged: "eat", "tea" and "ate" are anagrams of each other. The method groupAnagrams(String[] strings) receives an array of words and returns them as a List<List<String>>, one inner list per group of words that are anagrams of each other. The groups and the words within a group may come in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"] there are three groups: eat, tea and ate together; tan and nat together; and bat alone. A word with no anagram partner forms a group of one. The lesson asks for O(n * L * log L) time and O(n * L) extra space, where n is the number of words and L the length of the longest.
Approach: give every anagram the same key
The slow way compares every word against every other: n * n pairs, and each comparison needs its own sorting or counting. A hash map avoids the pairwise work if all words in one group can be made to produce the same key. The key must be identical for anagrams and different for non-anagrams.
Sorting the letters of a word does exactly that. "eat", "tea" and "ate" all become "aet", while "tan" and "nat" both become "ant" and "bat" becomes "abt". Two words are anagrams exactly when their sorted forms are equal, so the sorted form is a perfect group label.
The algorithm then makes one pass: sort each word's letters, use the result as the key in a Map<String, List<String>>, and add the original word to the list stored under that key. At the end, each list in the map is one complete group.
Step by step
- Create the map.
groupBySortedmaps a sorted string to the words that share it. AHashMapgives average O(1) lookups. - Loop over the words with an enhanced
for, naming each ones. - Build the sorted key. Strings can't be sorted directly, because they are immutable. Copy the letters into a
char[]withtoCharArray(), sort that array withArrays.sort, and turn it back into a string withnew String(temp). - Make sure a group exists. If the map does not contain the key yet, put a new empty
ArrayListunder it. - Add the word.
getreturns the list stored in the map itself, not a copy, so callingaddon it updates the group in place. - Return the groups.
groupBySorted.values()is aCollectionof the lists, but the method must return aList, so wrap it:new ArrayList<>(groupBySorted.values()).
The solution in Java
class Solution {
public List<List<String>> groupAnagrams(String[] strings) {
Map<String, List<String>> groupBySorted = new HashMap<>();
for (String s : strings) {
char[] temp = s.toCharArray();
Arrays.sort(temp);
String sortedString = new String(temp);
if (!groupBySorted.containsKey(sortedString)) {
groupBySorted.put(sortedString, new ArrayList<String>());
}
groupBySorted.get(sortedString).add(s);
}
return new ArrayList<>(groupBySorted.values());
}
}
The code uses classes from java.util (Map, HashMap, List, ArrayList and Arrays), so a standalone program needs import java.util.*;. For the sample input, the method returns the groups [eat, tea, ate], [bat] and [tan, nat]. Their order depends on how HashMap arranges its keys, which is unspecified. That is acceptable here because the problem allows any order, but it also means a test should compare groups, not rely on a fixed position.
Some Java details to watch:
- Use
new String(temp), nottemp.toString(). CallingtoString()on achar[]gives something like[C@1b6d3586, the array's type and identity, not its letters. Two arrays with equal contents would give different text, and every word would land in its own group. - The key is a
Stringfor a reason. Arrays use identity forequalsandhashCode, so achar[]can't serve as a map key. Strings compare by content. containsKeyplusputcan be shortened.groupBySorted.computeIfAbsent(sortedString, k -> new ArrayList<>()).add(s)does both in one call and behaves the same.
Complexity
For each of the n words, copying the letters costs O(L) and sorting them costs O(L log L), so the loop costs O(n * L * log L) in total. Map operations hash a key of up to L characters, which adds O(L) per word and does not change the bound. The map holds a sorted copy and a reference to each word, so the extra space is O(n * L).
A faster key
If the words only contain lowercase letters a to z, the sort can be replaced by counting. Count how many times each letter appears and use the 26 counts as the key. Anagrams have identical counts:
Map<String, List<String>> groups = new HashMap<>();
for (String s : strings) {
int[] count = new int[26];
for (char ch : s.toCharArray()) {
count[ch - 'a']++;
}
groups.computeIfAbsent(Arrays.toString(count), k -> new ArrayList<>()).add(s);
}
This version groups the sample the same way and takes O(n * L) time, because each word is read once. The price is that it only works for a fixed alphabet; the sorted key handles any characters.
Edge cases and common mistakes
- The empty string. Its sorted form is also the empty string, a valid key, so
[""]returns one group holding the empty word. Several empty strings share that group. - An empty array. The loop never runs and the method returns an empty list.
- Duplicates. Two equal words are anagrams of each other, so both are kept in the same group.
- Case.
"Eat"and"tea"are not grouped, because'E'sorts before lowercase letters and the keys differ. Lower-case the key first if case should be ignored. - Returning the wrong collection.
values()is a view of the map, not aList, so the code does not compile without wrapping it. Copying it into anArrayListalso detaches the result from the map.
