Sorting the strings takes O(k log(k)), but just doing a pass on each string and counting each character only takes O(k) time. You just allocate an array the size of your character set, and increment the value at that character's index. Finally, you write that array to a string (O(1), as it's determined by the size of your character set), and use that string as the key.