Задача "Sort Characters By Frequency"

Уровень: medium

Сегодня решала задачку с использованием не самой частой структуры данных - PriorityQueue. Думаю, стоит зафиксировать решение.

На вход получаем строку состоящую из английских букв (могут быть строчные и заглавные) и символов. Нужно вернуть строку эту же строку, но в отсортированном по убыванию порядке, исходя из того, сколько раз тот или иной символ в ней встречается. Если какие-то символы встречаются одинаковое кол-во раз, то вернуть их в любом порядке (оба ответа ок).

Например, на вход пришла строка: "a55dgggGPP"
Количество повторений символов в строке:
a - 1
5 - 2
g - 3
G - 1
P - 2
Ответ: "gggPP55aG" (варианты "ggg55PPaG", "ggg55PPGa", "gggPP55Ga" тоже ок)

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

Ссылочка на задачу, как всегда.

Алгоритм решения будет следующий:
1. Подсчитаем и сохраним частоту каждого символа в хэш-таблице
2. Закинем все символы в PriorityQueue, используя собственный Comparator (будем сравнивать частоты символов из хэш-таблицы и закидывать по убыванию - наверху кучи самый частый)
3. Извлекаем из кучи символы и записываем в результирущую строку (использую StringBuilder) в том количестве, в котором они хранятся в нашей хэш-таблице
4. Возвращаем результат

Кстати, есть еще решение, когда храним в куче и символы и частоты, так будет меньше get-ов (можно, поэксперементировать🙌)

Итак, код:

public String frequencySort(String s) {
    StringBuilder result = new StringBuilder();
    Map<Character, Integer> frequencyMap = new HashMap<>();

    for (char c : s.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }

    PriorityQueue<Character> heap = new PriorityQueue<>(
        (a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
    
    heap.addAll(frequencyMap.keySet());

    while (!heap.isEmpty()) {
        char sym = heap.poll();
        int count = frequencyMap.get(sym);
        for (int i = 0; i < count; i++) {
            result.append(sym);
        }
    }
    return result.toString();
}

Временная сложность: O(n log k), т.к. O(n) - добавление в хэш-таблицу (от количества символов в строке), O(k log k) - добавление в очередь, где k - кол-во уникальных символов в строке, извлечение из очереди и добавление в StringBuilder - O(f log k), где f - частота символа, а log k - скорость извлечения. Итого O (n log k) - т.к. повторяем операцию извлечения и присоединения для всех символов в строке. Но в худшем случае скорость будет O (n log n), если k = n, т.е. все символы уникальные.

Пространственная сложность: O(n), т.к. O(k) - хэш-таблица, O(k) - куча (очередь), O (n) - результирующая строка.

Кстати, здесь есть еще подход с решением с использованием массива символов, он чуть выиграет по памяти, но проиграет по скорости на больших строках с большим кол-вом повторений символов:) - хотя leetcode покажет более быстрый runtime.