Как подсчитать вхождения символа в строке

Иллюстрация букв алфавита

Строки — частая тема на собеседованиях. Перед интервью полезно потренироваться на задачах со строками. В этой статье объяснено, как подсчитать общее количество вхождений одного символа в строке, показаны несколько реализаций и даны практические замечания и тесты.

Примеры для понимания задачи

Пример 1: строка “she sells seashells by the seashore”, символ ‘s’.

str = “ s he s ell s s ea s hell s by the s ea s hore”

ch = ‘s’

Вхождений ‘s’ в строке — 8. Результат: 8.

Пример 2: строка “He threw three free throws”, символ ‘e’.

str = “H e thr e w thr ee fr ee throws”

ch = ‘e’

Вхождений ‘e’ — 6. Результат: 6.

Подход — пошагово

Пройтись по строке посимвольно.
Поддерживать счётчик вхождений (начинается с 0).
Для каждого символа сравнивать с искомым: если равно, увеличить счётчик.
Вернуть итоговый счёт.

Этот итеративный метод прост и эффективен для большинства задач. Важная характеристика — линейная временная сложность O(n) и константная дополнительная память O(1).

C++: программа для подсчёта вхождений символа

// C++ program to count occurrences
// of a given character in a string
#include 
#include 
using namespace std;

// Function to count the occurrences of
// the given character in the string
int countOccurrences(string str, char ch)
{
    // Counter variable
    int counter = 0;

    for (int i = 0; i < (int)str.length(); i++)
    {
        // check if the given character matches
        // with the character in the string
        if (str[i] == ch)
        {
            // if the given character matches with
            // the character in the string,
            // increment the counter variable
            counter++;
        }
    }
    return counter;
}

// Driver code
int main()
{
    string str1 = "she sells seashells by the seashore";
    char ch1 = 's';
    cout << "Input string 1: " << str1 << endl;
    cout << "Character " << ch1 << " has occurred " <<
         countOccurrences(str1, ch1) << " times in the given string." << endl;

    string str2 = "peter piper picked a peck of pickled peppers";
    char ch2 = 'p';
    cout << "Input string 2: " << str2 << endl;
    cout << "Character " << ch2 << " has occurred " <<
         countOccurrences(str2, ch2) << " times in the given string." << endl;

    string str3 = "I saw Susie sitting in a shoeshine shop";
    char ch3 = 'a';
    cout << "Input string 3: " << str3 << endl;
    cout << "Character " << ch3 << " has occurred " <<
         countOccurrences(str3, ch3) << " times in the given string." << endl;

    string str4 = "Near an ear, a nearer ear, a nearly eerie ear";
    char ch4 = 'r';
    cout << "Input string 4: " << str4 << endl;
    cout << "Character " << ch4 << " has occurred " <<
         countOccurrences(str4, ch4) << " times in the given string." << endl;

    string str5 = "He threw three free throws";
    char ch5 = 'e';
    cout << "Input string 5: " << str5 << endl;
    cout << "Character " << ch5 << " has occurred " <<
         countOccurrences(str5, ch5) << " times in the given string." << endl;

    return 0;
}

Вывод (пример):

Input string 1: she sells seashells by the seashore
Character s has occurred 8 times in the given string.
Input string 2: peter piper picked a peck of pickled peppers
Character p has occurred 9 times in the given string.
Input string 3: I saw Susie sitting in a shoeshine shop
Character a has occurred 2 times in the given string.
Input string 4: Near an ear, a nearer ear, a nearly eerie ear
Character r has occurred 8 times in the given string.
Input string 5: He threw three free throws
Character e has occurred 6 times in the given string.

Python: программа для подсчёта вхождений символа

# Python program to count occurrences
# of a given character in a string

# Function to count the occurrences of
# the given character in the string
def countOccurrences(s, ch):
    # Counter variable
    counter = 0

    for char in s:
        # check if the given character matches
        # with the character in the string
        if char == ch:
            # if the given character matches with
            # the character in the string,
            # increment the counter variable
            counter += 1
    return counter

# Driver code
str1 = "she sells seashells by the seashore"
ch1 = 's'
print("Input string 1:", str1)
print("Character", ch1, "has occured", countOccurrences(str1, ch1),"times in the given string.")

str2 = "peter piper picked a peck of pickled peppers"
ch2 = 'p'
print("Input string 2:", str2)
print("Character", ch2, "has occured", countOccurrences(str2, ch2),"times in the given string.")

str3 = "I saw Susie sitting in a shoeshine shop"
ch3 = 'a'
print("Input string 3:", str3)
print("Character", ch3, "has occured", countOccurrences(str3, ch3),"times in the given string.")

str4 = "Near an ear, a nearer ear, a nearly eerie ear"
ch4 = 'r'
print("Input string 4:", str4)
print("Character", ch4, "has occured", countOccurrences(str4, ch4),"times in the given string.")

str5 = "He threw three free throws"
ch5 = 'e'
print("Input string 5:", str5)
print("Character", ch5, "has occured", countOccurrences(str5, ch5),"times in the given string.")

Вывод (пример):

Input string 1: she sells seashells by the seashore
Character s has occurred 8 times in the given string.
Input string 2: peter piper picked a peck of pickled peppers
Character p has occurred 9 times in the given string.
Input string 3: I saw Susie sitting in a shoeshine shop
Character a has occurred 2 times in the given string.
Input string 4: Near an ear, a nearer ear, a nearly eerie ear
Character r has occurred 8 times in the given string.
Input string 5: He threw three free throws
Character e has occurred 6 times in the given string.

Совет: в Python есть встроенный метод str.count(ch), который делает то же самое короче: s.count(ch).

JavaScript: программа для подсчёта вхождений символа

// JavaScript program to count occurrences
// of a given character in a string

// Function to count the occurrences of
// the given character in the string
function countOccurrences(str, ch)
{
    // Counter variable
    var counter = 0;

    for (let i = 0; i < str.length; i++)
    {
        // check if the given character matches
        // with the character in the string
        if (str[i] == ch)
        {
            // if the given character matches with
            // the character in the string,
            // increment the counter variable
            counter++;
        }
    }
    return counter;
}

// Driver code
var str1 = "she sells seashells by the seashore";
var ch1 = 's';
document.write("Input string 1: " + str1 + "
");
document.write("Character " + ch1 + " has occurred " +
    countOccurrences(str1, ch1) + " times in the given string." + "
");

var str2 = "peter piper picked a peck of pickled peppers";
var ch2 = 'p';
document.write("Input string 2: " + str2 + "
");
document.write("Character " + ch2 + " has occurred " +
    countOccurrences(str2, ch2) + " times in the given string." + "
");

var str3 = "I saw Susie sitting in a shoeshine shop";
var ch3 = 'a';
document.write("Input string 3: " + str3 + "
");
document.write("Character " + ch3 + " has occurred " +
    countOccurrences(str3, ch3) + " times in the given string." + "
");

var str4 = "Near an ear, a nearer ear, a nearly eerie ear";
var ch4 = 'r';
document.write("Input string 4: " + str4 + "
");
document.write("Character " + ch4 + " has occurred " +
    countOccurrences(str4, ch4) + " times in the given string." + "
");

var str5 = "He threw three free throws";
var ch5 = 'e';
document.write("Input string 5: " + str5 + "
");
document.write("Character " + ch5 + " has occurred " +
    countOccurrences(str5, ch5) + " times in the given string." + "
");

Вывод (пример):

Input string 1: she sells seashells by the seashore
Character s has occurred 8 times in the given string.
Input string 2: peter piper picked a peck of pickled peppers
Character p has occurred 9 times in the given string.
Input string 3: I saw Susie sitting in a shoeshine shop
Character a has occurred 2 times in the given string.
Input string 4: Near an ear, a nearer ear, a nearly eerie ear
Character r has occurred 8 times in the given string.
Input string 5: He threw three free throws
Character e has occurred 6 times in the given string.

Другие методы решения

Рекурсия: работает, но добавляет глубину вызовов и не приносит преимуществ по сложности.
Регулярные выражения: useful для поиска шаблонов, но для одного символа избыточно.
Библиотечные функции: в C++ можно использовать std::count(begin, end, ch), в Python — s.count(ch), в JavaScript — комбинацию split/join или перебор с reduce.

Примеры альтернативных быстрых приёмов:

Python: s.count(ch) — O(n), очень лаконично.
C++: #include и std::count(str.begin(), str.end(), ch).
JavaScript: str.split(ch).length - 1 — работает, но создаёт массив и использует больше памяти.

Когда метод может «не сработать» — крайние случаи и подводные камни

Important: будьте внимательны с юникодом.

Регистрозависимость: ‘A’ ≠ ‘a’ — нужно приводить к одному регистру, если требуется нечувствительность к регистру.
Многобайтовые символы и комбинирующие знаки: в UTF-8 один визуальный символ (графема) может состоять из нескольких кодовых точек; простой перебор байтов или char в некоторых языках не даст корректного результата.
Нормализация: символы с диакритикой могут быть представлены по-разному (NFC vs NFD). Для сравнения графем нужно нормализовать строки.
Пробелы и невидимые символы: убедитесь в ожидаемом наборе символов (trim/replace если нужно).

Модель мышления (эвристика)

Представьте строку как последовательность ячеек. Подсчёт вхождений — это суммирование булевых совпадений по всем ячейкам. Это даёт O(n) и минимальную дополнительную память.

Блок с ключевыми числами

Временная сложность: O(n), где n — длина строки.
Память: O(1) для итеративного решения (не считая входной строки).
Альтернативы: библиотечные вызовы сохраняют ту же асимптотику, но могут отличаться по константам.

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

Функция возвращает целое число ≥ 0.
Для пустой строки возвращается 0.
Поведение с символами, которых нет в строке — 0.
Для нечувствительности к регистру добавлены преобразования регистров и к ним — тесты.
Тесты с юникодом/комбинациями обработаны, если задача этого требует.

Примеры тест-кейсов

s = “”, ch = ‘a’ → 0
s = “aaaa”, ch = ‘a’ → 4
s = “AbA”, ch = ‘a’ → 1 (регистр значим)
s = “AbA”, ch = ‘a’ с tolower → 2
s содержит комбинирующий акцент — проверить нормализацию

Шпаргалка: быстрые специальные приёмы

Python: s.count(ch)
C++: std::count(str.begin(), str.end(), ch)
JavaScript: str.split(ch).length - 1 (память O(n)) или ручной цикл

Чек-лист для собеседования

Кандидат объяснил сложность O(n).
Упомянул варианты с учётом регистра и юникода.
Написал проходящий тест для пустой строки.
Предложил альтернативы (std::count, str.count).

Резюме

Итеративный проход по строке — самый надёжный и понятный способ подсчитать вхождения символа. Для большинства задач он оптимален по времени и памяти. При работе с юникодом и визуальными символами стоит дополнительно использовать нормализацию или специализированные библиотеки.

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