Sort characters in a Python string by frequency

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


2 Answers
2

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:

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:

Counter

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

and its most_common() method:

most_common()

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


join

list

generator

"".join([...)

itertools.starmap

operator.mul

str.__mul__

return "".join(starmap(operator.mul, Counter(s).most_common()))

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

Thanks for contributing an answer to Code Review Stack Exchange!

But avoid …

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.