Sort Characters By Frequency

Question

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;
        }
    };

Answer 1

Shorter:

There are possibilities to make the code shorted without making it less correct/clear.

for(auto it = input.begin(); it!= input.end(); ++it)

Range loop could be used for this purpose.

        if(freq.find(*it) != freq.end())
        {
            freq[*it] += 1;
        }
        else
        {
            freq[*it] = 1;
        }

map zero initializes built in types when it creates the key-value pair. Source. So the check can be removed, and ++ used instead of +1. The change may also improve performance, but I don't think it will be much of a deal.

    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::vector has a constructor which takes iterator pair and constructs the container from that.

    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();
    }

In my opinion sort would be a better fit (making a heap is sorting too, but I think std::sort have potential to perform better), then do range for loop with the last 2 lines of the code inside of it. Currently intentions are less clear, though still good.

Style:

I think that having operator() in the outside class is confusing. If the clarity is really wanted, named lambda could be made, then passed to std::sort() or make_heap().

Theoretically input.length() can be bigger than maximum value of int, so std::size_t should be used, just to be nerd that cares about standard compliance.

Usage of map:

I think that map is the most clear solution for this problem. It lifts a lot of burden from the programmer. There are also possibilities that compiler vendor did some small map optimization (so everything will be in the automatic storage).

Copying the map into vector will probably cost nothing, since everything is POD, so it will decay into std::memset() or something similar (in case the map is small map, it will be even faster).

Sorting a vector should be fast as well, since char on the platform has theoretical maximum of 256 values.

The only thing that could be slightly sped up is putting the data into the result. reserve(input.length()) can be called on the result string so that it won't perform any additional memory allocations.

Performance:

The algorithm should be fast enough for most of the systems, unless insane blazing performance is needed (e.g. Facebook or similar).

Answer 2

I prefer the approach of user1118321, yet I suggest you use a std::unordered_map instead of array<int, ...> for the sake of type safety. However, I would modify the comparator such that if we have the same frequencies for the two input characters, we fall back to comparing by the character value:

#include <iostream>
#include <string>
#include <unordered_map>

using std::cout;
using std::endl;
using std::unordered_map;
using std::string;

class my_comparator
{
    std::unordered_map<char, size_t>* pmap;
public:

    my_comparator(std::unordered_map<char, size_t>* pmap) : pmap{pmap} {}

    bool operator()(char a, char b)
    {
        size_t frequency_a = (*pmap)[a];
        size_t frequency_b = (*pmap)[b];

        if (frequency_a == frequency_b)
        {
            // Break ties by characters.
            return a < b;
        }

        return frequency_a > frequency_b;
    }
};

void frequency_sort_string(std::string& str)
{
    std::unordered_map<char, size_t> frequency_map;

    for (char c : str)
    {
        frequency_map[c]++;
    }

    my_comparator my_cmp(&frequency_map);
    std::sort(str.begin(), str.end(), my_cmp);
}

int main()
{
    string text = "mississippi";
    cout << text << endl;
    frequency_sort_string(text);
    cout << text << endl;
}

Hope that helps.

Answer 3

Your approach is very easy to understand. I like it! I think you could improve it a little by doing the following things.

Simplify

The main thing I see is that this solution is more complicated than it needs to be. It's very understandable, but can be made even simpler. For example, instead of using a map of frequencies, why not just use an array? You know there are never more than 256 chars, so use that fact to your advantage:

std::array<int, 256> freq;

Once you've done that you can simply make a copy of the string and sort it using the frequency information. For example, you can make a Comparator object that knows the frequencies of the letters and sorts based on that. Something like this:

class FrequencyComparator {
public:
    FrequencyComparator(const std::array<int, 256>& frequencies) : _frequencies(frequencies) 
    {
    }

    bool operator()(const char& a, const char& b)
    {
        if (_frequencies[a] == _frequencies[b])
        {
            return (a > b);
        }

        if (_frequencies[a] > _frequencies[b])
        {
            return true;
        }

        return false;
    }

private:
    const std::array<int, 256>& _frequencies;
};

Once you have that, you can just call std::sort on it. Your ordering function would look like this:

std::string order(const std::string input)
{
    // Figure out the frequencies of the letters
    std::array<int, 256>   frequencies = { 0 };
    for (auto nextChar : input)
    {
        frequencies [ nextChar ]++;
    }

    // Sort the letters based on their frequency
    std::string result  = input;
    FrequencyComparator comparator(frequencies);
    std::sort(result.begin(), result.end(), comparator);

    return result;
}