## Description

https://leetcode.com/problems/sort-characters-by-frequency/

Given a string `s`

, sort it in decreasing order based on the frequency of characters, and return *the sorted string*.

**Example 1:**

Input:s = "tree"Output:"eert"Explanation:'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

**Example 2:**

Input:s = "cccaaa"Output:"aaaccc"Explanation:Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together.

**Example 3:**

Input:s = "Aabb"Output:"bbAa"Explanation:"bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

**Constraints:**

`1 <= s.length <= 5 * 10`

^{5}`s`

consists of English letters and digits.

## Explanation

Count the occurrences of characters and base on the number of occurrences to build a new string.

## Python Solution

```
class Solution:
def frequencySort(self, s: str) -> str:
counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1
priority_queue = []
for key, value in counter.items():
heapq.heappush(priority_queue, (-value, key))
results = ""
for k in range(len(priority_queue)):
pair = heapq.heappop(priority_queue)
for i in range(-pair[0]):
results += pair[1]
return results
```

- Time Complexity: O(N).
- Space Complexity: O(N).