Question:
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
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.
Example 2:
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.
Example 3:
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.
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.
