Most frequent character in range

Question

I have a string s of length n. What is the most efficient data structure / algorithm to use for finding the most frequent character in range i..j?

The string doesn't change over time, I just need to repeat queries that ask for the most frequent char among s[i], s[i + 1], ... , s[j].

Answer 1

The fastest would be to use an unordered_map or similar:

pair<char, int> fast(const string& s) {
    unordered_map<char, int> result;

    for(const auto i : s) ++result[i];
    return *max_element(cbegin(result), cend(result), [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; });
}

The lightest, memory-wise, would require a non-constant input which could be sorted, such that find_first_not_of or similar could be used:

pair<char, int> light(string& s) {
    pair<char, int> result;
    int start = 0;

    sort(begin(s), end(s));
    for(auto finish = s.find_first_not_of(s.front()); finish != string::npos; start = finish, finish = s.find_first_not_of(s[start], start)) if(const int second = finish - start; second > result.second) result = make_pair(s[start], second);
    if(const int second = size(s) - start; second > result.second) result = make_pair(s[start], second);
    return result;
}

It should be noted that both of these functions have the precondition of a non-empty string. Also if there is a tie for the most characters in the string both functions will return the character that is lexographically first as having the most.

Live Example

Answer 2

The most time-efficient algorithm, as has been suggested, is to store the frequencies of each character in an array. Note, however, that if you simply index the array with the characters, you may invoke undefined behaviour. Namely, if you are processing text that contains code points outside of the range 0x00-0x7F, such as text encoded with UTF-8, you may end up with a segmentation violation at best, and stack data corruption at worst:

char frequncies [256] = {};
frequencies ['á'] = 9; // Oops. If our implementation represents char using a
                       // signed eight-bit integer, we just referenced memory
                       // outside of our array bounds!

A solution that properly accounts for this would look something like the following:

template <typename charT>
charT most_frequent (const basic_string <charT>& str)
{
    constexpr auto charT_max = numeric_limits <charT>::max ();
    constexpr auto charT_min = numeric_limits <charT>::lowest ();
    size_t frequencies [charT_max - charT_min + 1] = {};

    for (auto c : str)
        ++frequencies [c - charT_min];

    charT most_frequent;
    size_t count = 0;
    for (charT c = charT_min; c < charT_max; ++c)
        if (frequencies [c - charT_min] > count)
        {
            most_frequent = c;
            count = frequencies [c - charT_min];
        }

    // We have to check charT_max outside of the loop,
    // as otherwise it will probably never terminate
    if (frequencies [charT_max - charT_min] > count)
        return charT_max;

    return most_frequent;
}

If you want to iterate over the same string multiple times, modify the above algorithm (as construct_array) to use a std::array <size_t, numeric_limits <charT>::max () - numeric_limits <charT>::lowest () + 1>. Then return that array instead of the max character after the first for loop and omit the part of the algorithm that finds the most frequent character. Construct a std::map <std::string, std::array <...>> in your top-level code and store the returned array in that. Then move the code for finding the most frequent character into that top-level code and use the cached count array:

char most_frequent (string s)
{
    static map <string, array <...>> cache;

    if (cache.count (s) == 0)
        map [s] = construct_array (s);
    // find the most frequent character, as above, replacing `frequencies`
    // with map [s], then return it
}

Now, this only works for whole strings. If you want to process relatively small substrings repeatedly, you should use the first version instead. Otherwise, I'd say that your best bet is probably to do something like the second solution, but partitioning the string into manageable chunks; that way, you can fetch most of the information from your cache, only having to recalculate the frequencies in the chunks in which your iterators reside.