Sort Characters by Frequency

Min-Heap

Problem

Given a string, sort it in decreasing order based on the frequency of characters.

For example:

Input:
"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.

Input:
"cccaaa"

Output:
"cccaaa"

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.

Input:
"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.

Thought Process

• This problem is similar to Top K Frequent Elements where we built a min-heap but instead in this problem we are using a max-heap in order to get the largest frequencies in order. We don't care about the top K so that is why we are not using a min-heap.

Solution

from heapq import *
class Solution:
    def frequencySort(self, s: str) -> str:
        heap = []
        freq = {}
        
        for i in s:
            if i not in freq:
                freq[i] = 0
            freq[i]+=1
        
        #making a max heap from the frequencies
        for char, count in freq.items():
            heappush(heap, (-count, char))
        
        string = ""
        
        while heap:
            frequency, c = heappop(heap)
            for _ in range(-frequency):
                string+=(c)
        
        return string

Key Points

• Using a max-heap so we get all the frequencies from largest to smallest in order

• While the heap is not empty, we will build a string, appending the most occuring characters first.

Time Complexity

• Time: $O(D*log(D))$ where ‘D’ is the number of distinct characters in the input string. This means, in the worst case, when all characters are unique the time complexity of the algorithm will be $O(N*log(N))$ where ‘N’ is the total number of characters in the string.

• Space: $O(N)$ as in the worst case, we need to store all the ‘N’ characters in the HashMap.