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