Редакция для Самое частое слово

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Разбор задачи «Самое частое слово»

1. Идея

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

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

Частоты удобно хранить в словаре «слово → количество». После подсчёта нужно найти максимум частоты и среди слов с этой частотой выбрать наименьшее по алфавиту — это одно линейное прохождение по словарю.

3. Алгоритм

Прочитать строку и разбить её на слова.
Построить словарь частот за один проход.
Найти максимальную частоту.
Среди слов с максимальной частотой выбрать лексикографически наименьшее и вывести его.

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

Словарь частот точно отражает число вхождений каждого слова. Условие «при равенстве — лексикографически наименьшее» однозначно доопределяет ответ, а перебор всех слов с максимальной частотой гарантированно находит нужное.

5. Сложность

Подсчёт частот и выбор ответа — линейны по суммарной длине строки: O(|s|) по времени и O(число различных слов) по памяти.

Код на C++17

#include <iostream>
#include <string>
#include <sstream>
#include <map>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    map<string, int> cnt;
    stringstream ss(s);
    string word;

    while (ss >> word) {
        cnt[word]++;
    }

    string best = "";
    int bestCount = -1;

    for (const auto &p : cnt) {
        const string &w = p.first;
        int c = p.second;
        if (c > bestCount) {
            bestCount = c;
            best = w;
        }
    }

    cout << best << '\n';
    return 0;
}

Код на Python 3

from collections import Counter

words = input().split()
cnt = Counter(words)
best = max(cnt.values())
ans = min(w for w in cnt if cnt[w] == best)
print(ans)