Задача с собеса Авито

На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.


Ограничения:
- длина строки от 1 до 5 * 10 ** 5
- строка состоит из английских букв в верхнем и нижнем регистре

наш чат алгоритмистов

Решение:
С помощью словаря подсчитаем частоты символов— O(N).Создадим массив корзин (bucket), где индекс — это частота символа.
(Максимальная возможная частота символа = N, если вся строка из одного символа.)
Разложим символы по корзинам в соответствии с их частотой — O(M), где M — число уникальных символов (M ≤ N). В конце пройдемся по корзине от самой высокой частоты к низкой и соберем результат — O(N)


def frequencySort(s):
    freq = {}
    for char in s:
         if chat not in freq:
              freq[char] = 0
        freq[char] += 1 
   

    buckets = [[] for _ in range(len(s) + 1)] 
    for char, count in freq.items():
        buckets[count].append(char) 
   
   
    result = []
    for count in range(len(buckets) - 1, -1, -1):
        for char in buckets[count]:
            result.append(char * count)
   
    return ''.join(result)

@algoses