Group Anagrams
MedPrompt
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
- There is no string in strs that can be rearranged to form
"bat". - The strings
"nat"and"tan"are anagrams as they can be rearranged to form each other. - The strings
"ate","eat", and"tea"are anagrams as they can be rearranged to form each other.
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is an optimization over the sorting method. Instead of sorting, we create a canonical key for each string based on its character counts. Two strings are anagrams if and only if they have the same character counts.
Algorithm
- Initialize a hash map
mapwherekeyis aStringandvalueis aList<String>. - Iterate through each string
sin the input arraystrs. - Create an integer array
countof size 26, initialized to zeros. - For each character
cins, incrementcount[c - 'a']. - Build a key string from the
countarray. A simple way is to append each count value preceded by a delimiter (e.g.,#) to aStringBuilder. - Use this generated
keyto store the original stringsin the map, creating a new list if the key is new. - After iterating through all strings, return a new list containing the values of the map.
Walkthrough
We use a hash map, similar to the previous approach. However, the key is generated differently. For each string, we compute its character frequency. Since the strings only contain lowercase English letters, we can use an integer array of size 26 for this. After counting, we need to convert this frequency array into a unique, hashable key. A common way is to create a string representation. For example, an array [1, 2, 0, ...] (one 'a', two 'b's) can be converted to a string like "1#2#0#...". We iterate through the input strs. For each string s, we calculate its character count array. We then build a key string from this count array. This key is used to store the original string s in the hash map. Finally, we return the lists of strings from the map's values. This method avoids the O(K log K) sorting cost, replacing it with a linear O(K) scan.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public List<List<String>> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) { return new ArrayList<>(); } 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 sb = new StringBuilder(); for (int i = 0; i < 26; i++) { sb.append('#'); sb.append(count[i]); } String key = sb.toString(); if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } map.get(key).add(s); } return new ArrayList<>(map.values()); }}Complexity
Time
O(N * K)
Space
O(N * K)
Trade-offs
Pros
Most efficient time complexity among the three approaches.
Avoids the log K factor associated with sorting.
Cons
The key generation is slightly more complex than simply sorting the string.
Solutions
Solution
class Solution {public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> d = new HashMap<>(); for (String s : strs) { char[] t = s.toCharArray(); Arrays.sort(t); String k = String.valueOf(t); d.computeIfAbsent(k, key->new ArrayList<>()).add(s); } return new ArrayList<>(d.values()); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.