Sort characters in a Python string by frequency

Question

I wrote a solution to the leetcode problem Sort characters by frequency and the solution passes 34/35 test cases. On the last test case, there is a "time limit exceeded" error with an input string of 100000+ "a" and "b" characters. How can the following code be optimized to handle an input of that size?

 def frequencySort(s): """ :type s: str :rtype: str """ freq = {} for i in s: if i in freq: freq[i] +=1 else: freq[i] = 1 output = "" newDict = sorted(freq.items(), key=lambda kv: kv[1],reverse = True) for k,v in newDict: for i in range(v): output += k return output 

Answer 1

The “set or increment dictionary value” logic

freq = {} for i in s: if i in freq: freq[i] +=1 else: freq[i] = 1 

can be simplified using a defaultdict:

from collections import defaultdict # ... freq = defaultdict(int) for i in s: freq[i] += 1 

But instead of creating, updating and sorting your own dictionary you can use the built-in Counter class:

A counter tool is provided to support convenient and rapid tallies.

and its most_common() method:

Return a list of the n most common elements and their counts from the most common to the least.

That simplifies the code to

from collections import Counter def frequencySort(s): """ :type s: str :rtype: str """ counter = Counter(s) output = "".join(char * freq for char, freq in counter.most_common()) return output 

Answer 2

The section:

for i in range(v): output += k 

Can be rewritten as:

output += k*v 

So that characters can be appended to the output in chunks this is much faster then doing it character by character

Answer 3

I think your code is getting a timeout because of an O(n^2) on the last part.

for k,v in newDict: for i in range(v): output += k 

The solution below maps every item in the ordered dict object to an ordered tuple, which is then much easier to iterate:

def solution(st): dict_ = {} for s in st: if s in dict_: dict_[s] += 1 else: dict_[s] = 1 items = sorted(dict_.items(), key=lambda kv: kv[1], reverse=True) string = "" for item in items: If item[1] != 0: string = string + item[0]*item[1] return string