Сортировать символы по частоте

Вход: "дерево"

Выход: "eert"

Объяснение: «e» появляется дважды, а «r» и «t» - один раз. Таким образом, "e" должно стоять перед "r" и "t". Следовательно, "eetr" тоже правильный ответ.

Я пробовал примерно так:

class Solution(object):
def frequencySort(self, s):
    """
    :type s: str
    :rtype: str
    """
    has = dict()
    l = list()
    for c in s:
        if c not in has:
            has[c] = 1
        else:
            has[c] += 1
    for k in sorted(has,key = has.get, reverse = True):
        for i in range(has[k]):
            l.extend(k)
    return ("".join(l))

но его O (n * m) n = длина строки, m = максимальное вхождение символа

Как я могу улучшить это до порядка n?