1. Идея

Нужно найти символ, который встречается в строке чаще всего.

Так как все символы — печатные ASCII, их коды лежат в небольшом диапазоне. Значит, удобно завести массив частот cnt размера 128, где cnt[code] хранит, сколько раз встретился символ с таким ASCII-кодом.

Дальше:

1. одним циклом считаем частоты всех символов строки;
2. вторым циклом перебираем ASCII-коды от 0 до 127 и выбираем символ с максимальной частотой.

Если несколько символов имеют одинаковую максимальную частоту, нужно взять символ с меньшим ASCII-кодом. Это автоматически получится, если идти по кодам слева направо и обновлять ответ только при строго большем значении частоты.

2. Наблюдения

Наблюдение 1. Символов мало

Длина строки может быть до 200000, но различных ASCII-кодов всего 128.

Поэтому вместо сложных структур данных достаточно обычного массива.

Наблюдение 2. Удобно считать по коду символа

Для каждого символа можно получить его код:

• в C++ — использовать значение char как индекс, но безопаснее приводить к unsigned char;
• в Python — использовать ord(c).

Тогда увеличение частоты выглядит просто: cnt[code] += 1.

Наблюдение 3. Как правильно обработать равенство частот

По условию, если максимум достигается у нескольких символов, нужен минимальный ASCII-код.

Если перебирать коды в порядке возрастания и обновлять ответ только когда найдено cnt[code] > bestFreq, то:

• первый найденный максимум сохранится;
• при равной частоте более поздний код уже не заменит ответ;
• значит, останется наименьший код среди всех с максимальной частотой.

3. Алгоритм

1. Считать строку s.
2. Создать массив cnt из 128 нулей.
3. Для каждого символа строки:
   • определить его ASCII-код;
   • увеличить соответствующий элемент массива cnt.
4. Завести переменные:
   • bestFreq = -1
   • bestCode = 0
5. Перебрать все коды от 0 до 127:
   • если cnt[code] > bestFreq, то обновить:
     • bestFreq = cnt[code]
     • bestCode = code
6. Вывести символ с кодом bestCode.

4. Почему это работает

Докажем, что алгоритм действительно находит нужный символ.

После первого цикла для каждого ASCII-кода code значение cnt[code] равно количеству вхождений символа с этим кодом в строку. Это верно, потому что для каждого символа строки мы ровно один раз увеличиваем его счётчик.

Теперь рассмотрим второй цикл по всем кодам от 0 до 127.

• Переменная bestFreq хранит максимальную частоту среди уже просмотренных кодов.
• Переменная bestCode хранит код символа, у которого эта частота достигается.

Когда встречается код code с частотой строго больше bestFreq, мы обязаны обновить ответ, потому что нашли более частый символ.

Если частота равна текущему максимуму, обновления не происходит. Поскольку коды перебираются в порядке возрастания, первым среди символов с максимальной частотой будет именно символ с минимальным ASCII-кодом. Он и останется в ответе до конца работы алгоритма.

Значит, после завершения второго цикла:

• bestFreq — максимальная частота символа в строке;
• bestCode — минимальный ASCII-код среди всех символов с такой частотой.

Следовательно, выведенный символ полностью соответствует условию задачи.

5. Сложность

Пусть длина строки равна n.

• Подсчёт частот работает за O(n).
• Поиск лучшего кода по массиву из 128 элементов работает за O(128), то есть за константу.

Итоговая сложность: O(n).

Память:

• массив из 128 чисел, то есть O(1) дополнительной памяти.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<int> cnt(128, 0);
    for (char c : s) {
        cnt[(unsigned char)c]++;
    }

    int bestCode = 0;
    int bestFreq = -1;

    for (int code = 0; code < 128; code++) {
        if (cnt[code] > bestFreq) {
            bestFreq = cnt[code];
            bestCode = code;
        }
    }

    cout << char(bestCode) << '\n';
    return 0;
}

7. Код на Python 3

s = input()

cnt = [0] * 128
for c in s:
    cnt[ord(c)] += 1

best_code = 0
best_freq = -1

for code in range(128):
    if cnt[code] > best_freq:
        best_freq = cnt[code]
        best_code = code

print(chr(best_code))