Гид по технологиям

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

4 min read Алгоритмы Обновлено 04 Dec 2025
Символ с наивысшей частотой в строке
Символ с наивысшей частотой в строке

Печати с буквами в стопке

Что такое задача (кратко)

Нужно найти символ (один символ) в строке, который встречается чаще всего. Если несколько символов имеют одинаковую максимальную частоту, обычно возвращают первый из встречающихся с этой частотой (в приведённых реализациях так и сделано).

Важное: здесь «символ» — это элемент строки. Для ASCII-подхода мы считаем, что каждый символ помещается в один байт. Для Unicode-строк (UTF-8) используйте словарь (map) по символам.

Примеры

  • Пример 1: “Makeuseof” — буква ‘e’ встречается 2 раза, остальные — 1 раз. Результат: ‘e’.
  • Пример 2: “She sees cheese” — буква ‘e’ встречается 6 раз. Результат: ‘e’.

Подход: частотный массив / хеширование

Идея простая:

  1. Создать структуру для подсчёта частоты каждого символа (фиксированный массив для ASCII или словарь для произвольных символов).
  2. Один раз пройти строку и увеличить счётчик для каждого символа.
  3. Отслеживать символ с максимальной частотой при проходе (или пройти по массиву/словарю, чтобы найти максимум).

Преимущества: 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: e

Python — реализация

# 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)).
  • Для стримовой обработки можно держать ограниченную структуру и счётчики, если память ограничена.

Мини‑методология: как выбрать подход в интервью

  1. Спросите о наборе символов (ASCII или Unicode).
  2. Согласуйте, учитывать ли регистр и пробелы.
  3. Предложите O(n) решение с частотным массивом/Map.
  4. Напишите код и добавьте небольшие тесты (см. раздел ниже).

Критерии приёмки

  • Для заданных примеров возвращает ожидаемые символы.
  • Работает за O(n) и не использует пропорционально много памяти для ASCII.
  • Корректно обрабатывает пустую строку (может возвратить специальный символ или пустое значение).

Тесты / примеры приёмки

  • “” → пустой результат (обработать отдельно).
  • “aaaa” → ‘a’.
  • “abbbc” → ‘b’.
  • “A a” с учётом регистра → выберите ожидаемое поведение (‘A’ или ‘ ‘ или ‘a’).
  • Юникод: “ååßßß” → для Unicode-подхода должно вернуть ‘ß’.

Краткое резюме

  • Частотный массив/хеш — быстрый и простой способ (обычно лучший выбор в интервью).
  • Для ASCII используйте массив размера 256; для Unicode — словарь/Map.
  • Проверьте требования по регистру и фильтрации символов перед реализацией.

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

Поделиться: X/Twitter Facebook LinkedIn Telegram
Автор
Редакция

Похожие материалы

Исправление ошибок Amazon Fire Stick
Техподдержка

Исправление ошибок Amazon Fire Stick

Скачать Microsoft Ultimate Word Games — руководство
Игры

Скачать Microsoft Ultimate Word Games — руководство

Удаление Antivirus Live и фальшивых антивирусов
Кибербезопасность

Удаление Antivirus Live и фальшивых антивирусов

Установка .NET Framework 2.0/3.0/3.5 в Windows 10
Windows

Установка .NET Framework 2.0/3.0/3.5 в Windows 10

Водяной знак в Word: как добавить и настроить
Инструкции

Водяной знак в Word: как добавить и настроить

Как изменить цвет панели задач в Windows
Инструкции

Как изменить цвет панели задач в Windows