Самый частый персонаж в диапазоне

Массив, в котором вы храните количество вхождений каждого символа. Вы увеличиваете соответствующее значение при однократном повторении строки. При этом вы можете запомнить текущий максимум в массиве; в качестве альтернативы найдите наибольшее значение в массиве в конце.

Псевдокод

arr = [0]
for ( char in string )
   arr[char]++
mostFrequent = highest(arr)

Выполните одну итерацию по массиву и для каждой позиции запомните, сколько вхождений каждого символа существует до этой позиции. Что-то вроде этого:

"abcdabc"

для индекса 0:

count['a'] = 1
count['b'] = 0
etc...

для индекса 1:

....
count['a'] = 1
count['b'] = 1
count['c'] = 0
etc...

для индекса 2:

....
count['a'] = 1
count['b'] = 1
count['c'] = 1
....

И так далее. Для индекса 6:

....
count['a'] = 2
count['b'] = 2
count['c'] = 2
count['d'] = 1
... all others are 0

После того, как вы вычислите этот массив, вы можете получить количество вхождений данной буквы в интервале (i, j) за постоянное время - просто вычислите count[j] - count[i-1] (здесь будьте осторожны с i = 0!).

Таким образом, для каждого запроса вам придется перебирать все буквы, а не все символы в интервале, и, таким образом, вместо перебора 10 ^ 6 символов вы будете передавать не более 128 (при условии, что у вас есть только символы ASCII).

Недостаток — вам нужно больше памяти, в зависимости от размера используемого вами алфавита.

Если вы хотите получить эффективные результаты на интервалах, вы можете построить интегральный вектор распределения для каждого индекса вашей последовательности. Затем, вычитая интегральные распределения в точках j+1 и i, можно получить распределение на интервале из s[i],s[i+1],...,s[j].

Далее следует некоторый псевдокод на Python. Я предполагаю, что ваши персонажи - это символы, следовательно, 256 записей о распространении.

def buildIntegralDistributions(s):
    IDs=[]        # integral distribution
    D=[0]*256
    IDs.append(D[:])
    for x in s:
        D[ord(x)]+=1
        IDs.append(D[:])
    return IDs

def getIntervalDistribution(IDs, i,j):
    D=[0]*256        
    for k in range(256):
        D[k]=IDs[j][k]-IDs[i][k]
    return D

s='abababbbb'
IDs=buildIntegralDistributions(s)
Dij=getIntervalDistribution(IDs, 2,4)

>>> s[2:4]
'ab'
>>> Dij[ord('a')]  # how many 'a'-s in s[2:4]?
1
>>> Dij[ord('b')]  # how many 'b'-s in s[2:4]?
1

Вам необходимо указать свои алгоритмические требования с точки зрения пространственной и временной сложности.

Если вы настаиваете на пространственной сложности O(1), простая сортировка (например, с использованием лексикографического упорядочения битов, если нет доступного оператора естественного сравнения) и подсчет количества вхождений самого высокого элемента даст вам O(N log N) временную сложность.

Если вы настаиваете на временной сложности O(N), используйте решение @Luchian Grigore, которое также требует пространственной сложности O(N) (ну, O(K) для K-буквенного алфавита).

string="something"
arrCount[string.length()];

после каждого доступа к строке вызовите freq()

freq(char accessedChar){
arrCount[string.indexOf(x)]+=1
}

чтобы получить наиболее часто встречающийся символ, вызовите string.charAt(arrCount.max())

предполагая, что строка постоянна, и разные i и j будут переданы вхождениям запроса.

Если вы хотите минимизировать время обработки, вы можете сделать

struct occurences{
    char c;
    std::list<int> positions;
};

и оставьте std::list<occurences> для каждого символа. для быстрого поиска вы можете оставить positions упорядоченным.

и если вы хотите минимизировать память, вы можете просто сохранить увеличивающееся целое число и перебрать i .. j

Как было предложено, наиболее эффективным по времени алгоритмом является сохранение частот каждого символа в массиве. Обратите внимание, однако, что если вы просто проиндексируете массив с символами, вы можете вызвать неопределенное поведение. А именно, если вы обрабатываете текст, который содержит кодовые точки за пределами диапазона 0x00-0x7F, например текст, закодированный с помощью UTF-8, в лучшем случае вы можете столкнуться с нарушением сегментации, а в худшем случае с повреждением данных стека:

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!

Решение, которое правильно учитывает это, будет выглядеть примерно так:

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

Если вы хотите перебирать одну и ту же строку несколько раз, измените приведенный выше алгоритм (как construct_array), чтобы использовать std::array <size_t, numeric_limits <charT>::max () - numeric_limits <charT>::lowest () + 1>. Затем верните этот массив вместо максимального символа после первого цикла for и опустите часть алгоритма, которая находит наиболее часто встречающийся символ. Создайте std::map <std::string, std::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
}

Теперь это работает только для целых строк. Если вы хотите многократно обрабатывать относительно небольшие подстроки, вам следует использовать первую версию. В противном случае я бы сказал, что вам лучше всего сделать что-то вроде второго решения, но разбивая строку на управляемые куски; таким образом, вы можете получить большую часть информации из своего кеша, только пересчитывая частоты в фрагментах, в которых находятся ваши итераторы.

Самым быстрым будет использование unordered_map или похожий:

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

Для самого легкого с точки зрения памяти потребуется непостоянный ввод, который можно отсортировать, например, find_first_not_of или аналогичный:

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

Следует отметить, что обе эти функции имеют предусловие непустой строки. Кроме того, если есть ничья для большинства символов в строке, обе функции вернут символ, который лексографически является первым как имеющий наибольшее количество символов.

Живой пример