# O(M*N) solution . NO sort and NO costly prime multiplication.

• Sorting is O(M log M * N) , where M is the average length of each string. Also how feasible is prime number multiplication for large inputs. For strings of size 20 or 50 or 100??

Here is a O(M*N) solution without sort and without costly prime multiplication. Most solutions use sort, my idea is to use a counter instead of sort. My hash construction is constant time and does not change with input size, O(26).

``````public List<List<String>> groupAnagrams(String[] strs) {

HashMap<String,List<String>> hm = new HashMap<String,List<String>>();

for(int i=0; i<strs.length; i++){
String eachString = strs[i];

//only lower-case letters. so array of size 26 is enough
int[] counter = new int[26];

//Iterate the string and increment corresponding index
//char - 'a' , so the index will be between 0 and 25
for(int j=0; j<eachString.length(); j++)
counter[eachString.charAt(j)-'a']++;

//Now iterate thorugh the counter array and construct the hash
//Eg: cat becomes 1a1c1t. caabbt becomes 2a2b1c1t
StringBuilder sb = new StringBuilder("");
for(int j=0; j<26; j++){
if(counter[j]>0){
sb.append(counter[j]);
sb.append((char) ('a'+j));
}
}

String hash = sb.toString();

//Chech if an entry exists in hash table already, else add a new one
if(!hm.containsKey(hash))

//Add this string to the list pointed by hash
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.