Day 5 of 10: Ingressive For Good Data Structures and Algorithm Challenge

Happy Sunday to you reading this!

It's the weekend and other than clothes, I got words to sort!

Today's task is as follows...

Instructions

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Testcase

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.

My Solution

Sorting based on frequency was familiar ground to me as I had solved a similar problem before. I created a dictionary to count the frequency of each alphabet in the string given. The keys contained each alphabet in the string and the corresponding value for each was the count of their occurrence.

Next, I sorted the dicionary according to the values in descending order. This part required a lot of research till i got the simplest code to make it work.

sorted(x.items(), key = lambda item: item[1], reverse = True)

Then, I formed the new word by iterating through the sorted dictionary and concatenating an empty string with the product of each key and its value(eg. e*3 gives eee).

And that's it! However, the memory usage(15.4mb) was less than just 40% of submissions.

I tried to find a way to optimise the code to use less memory. After a google search, I learnt that forming a word by concatenating uses more memory space and a join() method should be used instead.

So I modified my code to append the product of each key and value in the sorted dictionary to a list and converting the list to a string using "".join(). This used up 0.2mb less than the previous solution.

You can view my solution below.

And that's how i solved today's challenge.

Thank you for reading. Have a beautiful Sunday!