I solved this problem.
Problem Statement
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.
I solved this problem using heaps(since it was tagged under this category). I feel my solution is a bit verbose which includes building a vector from a map and so on.
Can you think of any redundancies that can be removed from this solution or any better way of doing it.
class CompareHeap
{
public:
bool operator()(const std::pair< char, int> &A, const std::pair< char , int > &B )
{
return (A.second < B.second);
}
};
class Solution {
public:
string frequencySort(string input) {
std::string answer = "";
std::map<char, int> freq;
for(auto it = input.begin(); it!= input.end(); ++it)
{
if(freq.find(*it) != freq.end())
{
freq[*it] += 1;
}
else
{
freq[*it] = 1;
}
}
std::vector<std::pair<char, int >> v;
std::transform(freq.begin(), freq.end(), std::back_inserter(v), [](std::pair<char , int > kv) {return kv;});
std::make_heap(v.begin(), v.end(), CompareHeap());
while(v.size() > 0)
{
std::pop_heap(v.begin(), v.end(), CompareHeap());
answer += std::string(v.back().second,v.back().first);
v.pop_back();
}
return answer;
}
};