Algorithmic problems: Sort Characters By Frequency

The third problem of the December leetcoding challenge https://leetcode.com/problems/sort-characters-by-frequency/ is a Medium category problem which was fun to solve and I could come up with the solution on my own in a fairly short amount of time compared to the previous problem. It's easy to come up with the solution if we are familiar with how Hash Maps or dictionaries work and use either the in-built sorting technique of our desired programming language or go fancy with a custom implementation of our favorite sorting algorithm.

Problem breakdown

The problem asks us to sort a string in decreasing order of its characters' frequency. The nice thing is that even if the frequencies of some characters in the string match, we can return the answer in any order. In case it wasn't the case, I would have used the alphanumeric order of the characters in the string as a tie-breaker.

My approach

Counting the frequency of each character in the string by iterating over the string and storing the characters as keys and their frequencies in the dictionary is a reasonable way to approach the problem. Then we simply we sort the keys in reverse order of their frequencies and return the keys the number of times they appear in the final answer. However, I wanted to use the Counter object of python and compare the results in terms of memory and time required to run the code.

Using plain Dictionary or hash_maps

def frequencySort(self, s: str) -> str:
        hash_map = {}
        for i, ch in enumerate(s):
            if ch not in hash_map:
                hash_map[ch] = 1
            else:
                hash_map[ch] += 1

        hash_map = {k:v for k, v in sorted(hash_map.items(), key= lambda item: item[1], reverse=True)}

        return "".join([k*v for k, v in hash_map.items()])

Space and Time needed

Using Counter objects

the counter objects are a flavor of dictionaries in python that provide an efficient way to count items in an iterable. We simply pass the iterable e.g a list or in this case our string to the Counter instance and it will return a dictionary of the characters with their counts or frequencies.

def frequencySort(self, s: str) -> str:
        hash_map = Counter(s)

        hash_map = {k:v for k, v in sorted(hash_map.items(), key= lambda item: item[1], reverse=True)}

        return "".join([*Counter(hash_map).elements()])

the resultant code looks much cleaner and consise and you bet it's more efficent.

Time and Space Complexity

Overall for both approaches

We took up extra space so O(n) space complexity

and the sorting and iterating through the dictionary items take O(nlogn) + O(n) time.

That's a wrap for today. I loved using the Counter object for this problem and felt quite cool while writing the list comprehensions. Heh! I bet using a different sorting function e.g bucket sort or using a priority queue should also be an interesting approach. Send your thoughts and your approach to the problem as well.