Как посчитать количество вхождений символа в строке
Примеры для понимания задачи
Пример 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
Пример 2: Пусть дана строка “He threw three free throws” и символ ‘e’.
str = “H e thr e w thr ee fr ee throws”
ch = ‘e’
В данной строке символ e встречается шесть раз.
Вывод: 6
Подход к решению
Идея простая и часто используемая на собеседованиях:
- Инициализируйте счётчик (counter) нулём.
- Пройдите строку посимвольно (итерация по индексам или по символам).
- Для каждого символа сравните его с заданным символом; если совпадает — увеличьте счётчик.
- Верните значение счётчика.
Сложность: временная O(n), где n — длина строки; дополнительная память O(1).
C++ программа для подсчёта вхождений символа в строке
Ниже — реализация на C++. Комментарии и выводы переведены на русский.
// C++ программа для подсчёта
// вхождений заданного символа в строке
#include
#include
using namespace std;
// Функция считает вхождения символа ch в строке str
int countOccurrences(string str, char ch)
{
// Счётчик
int counter = 0;
for (int i = 0; i < str.length(); i++)
{
// если символ совпадает — увеличиваем счётчик
if (str[i] == ch)
{
counter++;
}
}
return counter;
}
// Тесты
int main()
{
string str1 = "she sells seashells by the seashore";
char ch1 = 's';
cout << "Входная строка 1: " << str1 << endl;
cout << "Символ " << ch1 << " встретился " << countOccurrences(str1, ch1)
<< " раз(а) в строке." << endl;
string str2 = "peter piper picked a peck of pickled peppers";
char ch2 = 'p';
cout << "Входная строка 2: " << str2 << endl;
cout << "Символ " << ch2 << " встретился " << countOccurrences(str2, ch2)
<< " раз(а) в строке." << endl;
string str3 = "I saw Susie sitting in a shoeshine shop";
char ch3 = 'a';
cout << "Входная строка 3: " << str3 << endl;
cout << "Символ " << ch3 << " встретился " << countOccurrences(str3, ch3)
<< " раз(а) в строке." << endl;
string str4 = "Near an ear, a nearer ear, a nearly eerie ear";
char ch4 = 'r';
cout << "Входная строка 4: " << str4 << endl;
cout << "Символ " << ch4 << " встретился " << countOccurrences(str4, ch4)
<< " раз(а) в строке." << endl;
string str5 = "He threw three free throws";
char ch5 = 'e';
cout << "Входная строка 5: " << str5 << endl;
cout << "Символ " << ch5 << " встретился " << countOccurrences(str5, ch5)
<< " раз(а) в строке." << endl;
return 0;
} Вывод (пример):
Входная строка 1: she sells seashells by the seashore
Символ s встретился 8 раз(а) в строке.
Входная строка 2: peter piper picked a peck of pickled peppers
Символ p встретился 9 раз(а) в строке.
Входная строка 3: I saw Susie sitting in a shoeshine shop
Символ a встретился 2 раз(а) в строке.
Входная строка 4: Near an ear, a nearer ear, a nearly eerie ear
Символ r встретился 8 раз(а) в строке.
Входная строка 5: He threw three free throws
Символ e встретился 6 раз(а) в строке.Python программа для подсчёта вхождений символа в строке
Реализация на Python — компактная и читаемая.
# Python программа для подсчёта
# вхождений заданного символа в строке
# Функция считает вхождения символа ch в строке str
def countOccurrences(s, ch):
# Счётчик
counter = 0
for char in s:
# если символ совпадает — увеличиваем счётчик
if char == ch:
counter += 1
return counter
# Тесты
str1 = "she sells seashells by the seashore"
ch1 = 's'
print("Входная строка 1:", str1)
print("Символ", ch1, "встретился", countOccurrences(str1, ch1), "раз(а) в строке.")
str2 = "peter piper picked a peck of pickled peppers"
ch2 = 'p'
print("Входная строка 2:", str2)
print("Символ", ch2, "встретился", countOccurrences(str2, ch2), "раз(а) в строке.")
str3 = "I saw Susie sitting in a shoeshine shop"
ch3 = 'a'
print("Входная строка 3:", str3)
print("Символ", ch3, "встретился", countOccurrences(str3, ch3), "раз(а) в строке.")
str4 = "Near an ear, a nearer ear, a nearly eerie ear"
ch4 = 'r'
print("Входная строка 4:", str4)
print("Символ", ch4, "встретился", countOccurrences(str4, ch4), "раз(а) в строке.")
str5 = "He threw three free throws"
ch5 = 'e'
print("Входная строка 5:", str5)
print("Символ", ch5, "встретился", countOccurrences(str5, ch5), "раз(а) в строке.")Вывод (пример):
Входная строка 1: she sells seashells by the seashore
Символ s встретился 8 раз(а) в строке.
Входная строка 2: peter piper picked a peck of pickled peppers
Символ p встретился 9 раз(а) в строке.
Входная строка 3: I saw Susie sitting in a shoeshine shop
Символ a встретился 2 раз(а) в строке.
Входная строка 4: Near an ear, a nearer ear, a nearly eerie ear
Символ r встретился 8 раз(а) в строке.
Входная строка 5: He threw three free throws
Символ e встретился 6 раз(а) в строке.JavaScript программа для подсчёта вхождений символа в строке
Реализация на JavaScript — для браузера или Node.js.
// JavaScript программа для подсчёта
// вхождений заданного символа в строке
// Функция считает вхождения символа ch в строке str
function countOccurrences(str, ch)
{
// Счётчик
var counter = 0;
for (let i = 0; i < str.length; i++)
{
// если символ совпадает — увеличиваем счётчик
if (str[i] == ch)
{
counter++;
}
}
return counter;
}
// Тесты
var str1 = "she sells seashells by the seashore";
var ch1 = 's';
document.write("Входная строка 1: " + str1 + "
");
document.write("Символ " + ch1 + " встретился " + countOccurrences(str1, ch1) + " раз(а) в строке." + "
");
var str2 = "peter piper picked a peck of pickled peppers";
var ch2 = 'p';
document.write("Входная строка 2: " + str2 + "
");
document.write("Символ " + ch2 + " встретился " + countOccurrences(str2, ch2) + " раз(а) в строке." + "
");
var str3 = "I saw Susie sitting in a shoeshine shop";
var ch3 = 'a';
document.write("Входная строка 3: " + str3 + "
");
document.write("Символ " + ch3 + " встретился " + countOccurrences(str3, ch3) + " раз(а) в строке." + "
");
var str4 = "Near an ear, a nearer ear, a nearly eerie ear";
var ch4 = 'r';
document.write("Входная строка 4: " + str4 + "
");
document.write("Символ " + ch4 + " встретился " + countOccurrences(str4, ch4) + " раз(а) в строке." + "
");
var str5 = "He threw three free throws";
var ch5 = 'e';
document.write("Входная строка 5: " + str5 + "
");
document.write("Символ " + ch5 + " встретился " + countOccurrences(str5, ch5) + " раз(а) в строке." + "
");Вывод (пример):
Входная строка 1: she sells seashells by the seashore
Символ s встретился 8 раз(а) в строке.
Входная строка 2: peter piper picked a peck of pickled peppers
Символ p встретился 9 раз(а) в строке.
Входная строка 3: I saw Susie sitting in a shoeshine shop
Символ a встретился 2 раз(а) в строке.
Входная строка 4: Near an ear, a nearer ear, a nearly eerie ear
Символ r встретился 8 раз(а) в строке.
Входная строка 5: He threw three free throws
Символ e встретился 6 раз(а) в строке.Другие методы решения
- Использование встроенных библиотек: в C++ можно применять std::count(begin, end, ch), в Python — s.count(ch).
- Регулярные выражения: полезны, если нужно учитывать множества символов или флаги (например, флаг регистронезависимости).
- Рекурсия: теоретически возможна, но для длинных строк вызывает лишнюю глубину вызовов.
- Потоковые/функциональные подходы: map/reduce или подсчёт с помощью генераторов в Python.
Когда базовый итеративный метод не подойдёт
- Unicode и комбинирующие символы: если требуется считать визуальные символы (графемы) вместо кодовых точек, простой перебор char/bytes может дать некорректный результат.
- Регистронезависимый подсчёт: если нужно считать ‘A’ и ‘a’ как одно, предварительно нормализуйте регистр и форму Unicode.
- Очень большие объёмы данных в потоке: имеет смысл использовать стрим-подход и счётчики на лету.
Мини-методология для интервью
- Задайте требования: регистр важен? Unicode? Нужно ли считать подстроки дольше одного символа?
- Назовите сложность алгоритма (O(n), O(1) доп. память).
- Покажите простую итеративную реализацию.
- Обсудите альтернативы и крайние случаи.
- Напишите тесты для пустой строки, строки без совпадений, строки с только совпадениями, Unicode.
Фактбокс — ключевые числа
- Временная сложность: O(n).
- Дополнительная память: O(1).
- Типичный набор тестов: 5–7 кейсов (пустая строка, все совпадают, нет совпадений, смешанный регистр, Unicode).
Чеклист для собеседования
- Кандидат проверил требования к регистру и Unicode.
- Кандидат назвал сложность алгоритма и обоснование.
- Реализация корректно работает для пустой строки.
- Добавлены автотесты или сценарии проверки.
- Рассмотрены альтернативные реализации (std::count, str.count, regex).
Критерии приёмки
- Функция возвращает корректное целое число для всех тестовых случаев.
- Обрабатываются пустые строки и строки без совпадений.
- (Опционально) Поддержка регистронезависимого поиска и базовой нормализации Unicode.
Итог
Итеративный проход по строке — самый простой и эффективный способ подсчитать вхождения символа. Для большинства задач на собеседовании этого достаточно, но при работе с Unicode или особыми требованиями к нормализации стоит уточнить требования и при необходимости использовать библиотечные функции или дополнительные трансформации строки.
Автор
Редакция
Похожие материалы
Frontend
CSS font-family: как менять шрифты на сайте
Финансы
График амортизации кредита в Excel — пошагово
Аппаратное обеспечение
Разгон Raspberry Pi 4 — безопасный пошаговый гид
Mac
Как запустить Windows 11 на Mac — варианты и советы
Безопасность
Мошенничество с возвратом средств через техподдержку
Дизайн