# Java 20ms solution using counting sort

• Given a string "abddb", the most popular solution use "Arrays.sort(['a','b','d','d','b'])" to get the key. This solution has time complexity O(n*(mlog m)). Using the counting sort, the time complexity can be reduced to
O(n
(m + 26))

``````public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> myMap = new HashMap<String, List<String>>();

for (String str : strs) {
String ordered = orderedString(str);
if (!myMap.containsKey(ordered)) {
myMap.put(ordered, new ArrayList<String>());
}

}

for (String key : myMap.keySet()) {
Collections.sort(myMap.get(key));
}

return new ArrayList<List<String>>(myMap.values());
}

String orderedString(String str) {
//use count sort O(m + 26) where m = str.length();
//space
// if str = "a b b f"
if (str == null || str.length() == 0) return "";
char[] output = new char[str.length()];
int[] count = new int[26];

//count = [1 2 0 0 0 1 0 0... 0]
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a'] += 1;
}

//count = [0 1 3 3 3 3 4 ... 4];
int preTotal = 0;
for (int i = 0; i < count.length; i++) {
int tmp = count[i];
//number of iterm less than i
count[i] = preTotal;
preTotal += tmp;
}

for (int i = 0; i < str.length(); i++) {
output[count[str.charAt(i) - 'a']] = str.charAt(i);
//next position
count[str.charAt(i) - 'a'] += 1;
}

return new String(output);

}
}``````

• I have a similar idea, but yours is much faster than mine :)

• BTW, you seem to have forgotten to comment out the following line:

``count[str.charAt(i) - 'a'] += 1;``

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