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
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