Sort Characters By Frequency-Leetcode Solution & intuition

Image for post
Image for post

Question:

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

Example 1:

Input:
"tree"

Example 2:

Input:
"cccaaa"

Example 3:

Input:
"Aabb"

Approach:

How do we approach this problem?

This question is saying we have to sort the string according to the occurrences of the characters in it. That means the first thing we need to do is calculate the occurrence. Isn’t it?

How do we calculate the occurrences of each character in a string?

Solution: it’s simple. HashMap (The mother of data structures )

Yeah, we going to use a HashMap to calculate the occurrences of each character in a string.

Take an example:

“tree” would look like {“t”: 1, “r”: 1, “e”: 2}

We know that to sort the characters, we need their occurrence, and we got the existence. So now the problem is, how are we going to sort them? So let’s run through an example:

“tree” would result in “eert” or “eetr”

“Aabb” would result in “bbaA” or “bbAa”

As you can see we have to get the highest occurring character in every stage while creating the resultant string. So is there anything that would give us the highest occurring character at any moment.

Ans: Heap

Yes, Heap. And what kind of Heap?

Ans: MaxHeap

So how maxHeap is gonna help? So what we are gonna do is put every character into the heap and pass their respective occurrences as their comparing parameters. So whenever we poll a character from the heap we are gonna get the maximum occurring character and then we build our resultant string.

So now we have fully solved the problem as you can see we broke down our problem into smaller parts and keep on solving as they require anything like any required ds or logic for any smaller problem. So let’s jump into the code now.

Time Complexity: O(n log n) <- absolute scale

Space Complexity: O(n)

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

If you liked it more than anything then clap and share. See you in the next blog.

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Former Intern @Vedantu, Codeforces(Expert)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store