In most cases such complexity is efficient. Try to switch to unordered map,set. Also for faster io speed use ios_base::sync_with_stdio(false);

You can improve the complexity by storing a set of strings for each frequency. When you modify the count of a certain word you can move it into the appropriate set. Then you can just read the string at the start of the set of the maximum count which you are maintaining.

Also to improve your speed 1. use stdio (scanf/printf) when there are long strings or even getchar 2. once you read in a string cache it using map to an integer so you can avoid passing around heavy strings and just use integers.