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))
hm.put(hash,new LinkedList<String>());
//Add this string to the list pointed by hash
hm.get(hash).add(eachString);
}
```