Как найти символ с наивысшей частотой в строке

Что такое задача (кратко)
Нужно найти символ (один символ) в строке, который встречается чаще всего. Если несколько символов имеют одинаковую максимальную частоту, обычно возвращают первый из встречающихся с этой частотой (в приведённых реализациях так и сделано).
Важное: здесь «символ» — это элемент строки. Для ASCII-подхода мы считаем, что каждый символ помещается в один байт. Для Unicode-строк (UTF-8) используйте словарь (map) по символам.
Примеры
- Пример 1: “Makeuseof” — буква ‘e’ встречается 2 раза, остальные — 1 раз. Результат: ‘e’.
- Пример 2: “She sees cheese” — буква ‘e’ встречается 6 раз. Результат: ‘e’.
Подход: частотный массив / хеширование
Идея простая:
- Создать структуру для подсчёта частоты каждого символа (фиксированный массив для ASCII или словарь для произвольных символов).
- Один раз пройти строку и увеличить счётчик для каждого символа.
- Отслеживать символ с максимальной частотой при проходе (или пройти по массиву/словарю, чтобы найти максимум).
Преимущества: O(n) по времени, O(1) по дополнительной памяти для фиксированного алфавита (ASCII) или O(k) для словаря (k — число уникальных символов).
Важно: если нужно учитывать регистр, пробелы или пунктуацию — явно решите это до подсчёта (например, приводите к нижнему регистру или фильтруете символы).
C++ — реализация
// C++ program to find the character
// having the highest frequency in a string
#include
#include
#define ASCII_SIZE 256
using namespace std;
char maxFrequencyChar(const string &str)
{
// Массив для частоты каждого символа, инициализирован нулями
int frequency[ASCII_SIZE] = {0};
int maxFrequency = -1;
char maxFrequencyChar = '\0';
// Один проход по строке: считаем и сразу обновляем максимум
for (char c : str)
{
unsigned char uc = static_cast(c);
frequency[uc]++;
if (maxFrequency < frequency[uc])
{
maxFrequency = frequency[uc];
maxFrequencyChar = c;
}
}
return maxFrequencyChar;
}
int main()
{
string str1 = "Which witch is which?";
cout << "str1: " << str1 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str1) << endl;
string str2 = "He threw three free throws";
cout << "str2: " << str2 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str2) << endl;
string str3 = "Eddie edited it";
cout << "str3: " << str3 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str3) << endl;
string str4 = "Makeuseof";
cout << "str4: " << str4 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str4) << endl;
string str5 = "She sees cheese";
cout << "str5: " << str5 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str5) << endl;
return 0;
} Вывод (примерный):
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: ePython — реализация
# Python program to find the character
# having the highest frequency in a string
ASCII_SIZE = 256
def maxFrequencyChar(s):
# Массив частот для ASCII
frequency = [0] * ASCII_SIZE
maxFrequency = -1
maxFrequencyChar = ''
# Считаем частоты
for ch in s:
frequency[ord(ch)] += 1
# Находим первый символ с максимальной частотой
for ch in s:
if maxFrequency < frequency[ord(ch)]:
maxFrequency = frequency[ord(ch)]
maxFrequencyChar = ch
return maxFrequencyChar
# Примеры
if __name__ == '__main__':
examples = [
"Which witch is which?",
"He threw three free throws",
"Eddie edited it",
"Makeuseof",
"She sees cheese"
]
for s in examples:
print("str:", s)
print("The highest frequency character is:", maxFrequencyChar(s))Вывод будет соответствовать примерам выше.
C — реализация (корректный C-код)
// C program to find the character
// having the highest frequency in a string
#include
#include
#define ASCII_SIZE 256
char maxFrequencyChar(char *str)
{
int frequency[ASCII_SIZE] = {0};
int lenOfStr = strlen(str);
int maxFrequency = 0;
char maxFrequencyChar = '\0';
for (int i = 0; i < lenOfStr; i++)
{
unsigned char uc = (unsigned char)str[i];
frequency[uc]++;
if (maxFrequency < frequency[uc])
{
maxFrequency = frequency[uc];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
int main()
{
char str1[] = "Which witch is which?";
printf("str1: %s\n", str1);
printf("The highest frequency character is: %c\n", maxFrequencyChar(str1));
char str2[] = "He threw three free throws";
printf("str2: %s\n", str2);
printf("The highest frequency character is: %c\n", maxFrequencyChar(str2));
char str3[] = "Eddie edited it";
printf("str3: %s\n", str3);
printf("The highest frequency character is: %c\n", maxFrequencyChar(str3));
char str4[] = "Makeuseof";
printf("str4: %s\n", str4);
printf("The highest frequency character is: %c\n", maxFrequencyChar(str4));
char str5[] = "She sees cheese";
printf("str5: %s\n", str5);
printf("The highest frequency character is: %c\n", maxFrequencyChar(str5));
return 0;
} JavaScript — реализация
// JavaScript program to find the character
// having the highest frequency in a string
function maxFrequencyChar(str) {
const ASCII_SIZE = 256;
const frequency = new Array(ASCII_SIZE).fill(0);
let maxFrequency = -1;
let maxFrequencyChar = '';
for (let i = 0; i < str.length; i++) {
const code = str.charCodeAt(i);
frequency[code] += 1;
if (maxFrequency < frequency[code]) {
maxFrequency = frequency[code];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Примеры
const examples = [
"Which witch is which?",
"He threw three free throws",
"Eddie edited it",
"Makeuseof",
"She sees cheese"
];
examples.forEach(s => {
console.log('str:', s);
console.log('The highest frequency character is:', maxFrequencyChar(s));
});Сложность (время и память)
- Время: O(n), где n — длина строки (один проход для подсчёта).
- Память: O(1) для фиксированного алфавита (например, ASCII — массив длиной 256), или O(k) для словаря/Map, где k — количество уникальных символов.
Факт: при использовании словаря для Unicode нужно учитывать, что число уникальных символов может значительно превышать 256.
Подводные камни и когда этот метод может не подойти
- Чувствительность к регистру: ‘A’ и ‘a’ считаются разными символами. Приведение к одному регистру изменит результат.
- Пробелы и знаки препинания могут стать ответом, если их не фильтровать.
- Для UTF-8 строк (многоязычный текст) нельзя индексировать байт-значения; используйте Map/словарь или итерируйте по юникодным кодовым точкам.
- Если нужно вернуть все символы с максимальной частотой, текущие реализации возвращают только первый найденный.
Альтернативные подходы
- Сортировка символов (O(n log n)) и поиск максимальной группы — проще для некоторых языков, но медленнее.
- Использовать готовый счётчик (Python: collections.Counter.most_common(1)).
- Для стримовой обработки можно держать ограниченную структуру и счётчики, если память ограничена.
Мини‑методология: как выбрать подход в интервью
- Спросите о наборе символов (ASCII или Unicode).
- Согласуйте, учитывать ли регистр и пробелы.
- Предложите O(n) решение с частотным массивом/Map.
- Напишите код и добавьте небольшие тесты (см. раздел ниже).
Критерии приёмки
- Для заданных примеров возвращает ожидаемые символы.
- Работает за O(n) и не использует пропорционально много памяти для ASCII.
- Корректно обрабатывает пустую строку (может возвратить специальный символ или пустое значение).
Тесты / примеры приёмки
- “” → пустой результат (обработать отдельно).
- “aaaa” → ‘a’.
- “abbbc” → ‘b’.
- “A a” с учётом регистра → выберите ожидаемое поведение (‘A’ или ‘ ‘ или ‘a’).
- Юникод: “ååßßß” → для Unicode-подхода должно вернуть ‘ß’.
Краткое резюме
- Частотный массив/хеш — быстрый и простой способ (обычно лучший выбор в интервью).
- Для ASCII используйте массив размера 256; для Unicode — словарь/Map.
- Проверьте требования по регистру и фильтрации символов перед реализацией.
Важно: если работаете с реальным многоязычным текстом, всегда проверяйте, как ваш язык программирования и выбор структуры данных обрабатывают юникодные символы.
Похожие материалы
Исправление ошибок Amazon Fire Stick
Скачать Microsoft Ultimate Word Games — руководство
Удаление Antivirus Live и фальшивых антивирусов
Установка .NET Framework 2.0/3.0/3.5 в Windows 10
Водяной знак в Word: как добавить и настроить