Count a Character

Q: Можно ли использовать встроенную функцию подсчёта на собеседовании?

Обычно да, если ты можешь объяснить, сколько это стоит. str.count в Python и подобные функции всё равно просматривают всю строку, поэтому их сложность — O(n) . Будь готов написать цикл, если интервьюер попросит.

НовичокМассивы и строки

+10

Дана строка s и одна буква c. Верните количество появлений c в s. Сопоставление чувствительно к регистру: B и b — разные символы.

Функция

countChar(s: string, c: string) → integer

sstring: строка английских букв для поиска
cstring: единственная буква, которую нужно посчитать
Возвращаетinteger: сколько символов в s равны c

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только английские буквы (a–z, A–Z).
c — это ровно одна английская буква.

Примеры

Ввод: s = "Mississippi"c = "s"
Вывод: 4
Пояснение: В слове Mississippi буква s стоит на индексах 2, 3, 5 и 6, поэтому ответ — 4.

Ввод: s = "Banana"c = "b"
Вывод: 0
Пояснение: Banana начинается с заглавной B, а ты ищешь строчную b. Совпадений нет, поэтому ответ — 0.

Дополнительный вопрос

Что, если c может быть словом из нескольких букв, например ss? Считаются ли пересекающиеся совпадения и как изменится ваш цикл?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Любой символ в s может быть c, поэтому проверь каждый символ один раз и посчитай совпадения. Учитывай регистр: заглавная буква — это другой символ.

Удалите каждую c и сравните длины

Идея

Создайте копию s, удалив из неё все c. Каждое удаление укорачивает копию на один символ, поэтому разница в длине и есть количество. Для Mississippi копия будет Miiippi: 11 минус 7 равно 4.

Время выполнения составляет O(n), но для копии требуется дополнительная память O(n), которая счётчику не нужна.

Алгоритм

Создай копию s, пропустив каждый символ, равный c.
Измерь длину s и длину копии.
Верни длину s минус длина копии.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Один проход со счётчиком

Идея

Считайте символы на ходу, не создавая копию. Счётчик начинается с 0 и увеличивается на 1 для каждого символа, равного c. Простое сравнение на равенство не позволяет заглавной букве совпасть со строчной.

Каждый символ сравнивается один раз, и хранится только счётчик: время O(n), память O(1). Ни одно решение не работает быстрее, чем за O(n), потому что пропущенный символ может оказаться ещё одной c.

Алгоритм

Считай целевую букву из c и установи count = 0.
Просматривай s по одному символу за раз.
Если символ совпадает с целевым, прибавь 1 к count.
Верни count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Ловушки и крайние случаи

Игнорирование регистра. Перевод обеих сторон в нижний регистр приводит к тому, что Banana и b возвращают 1; правильный ответ — 0.
Сравнение символа со строкой. В Java, C, C++, C# и Go c передаётся как строка, а s[i] или s.charAt(i) — это один символ. Получи c[0] (или c.charAt(0)) один раз перед циклом.
Сравнение строк с помощью == в Java. String.valueOf(s.charAt(i)) == c сравнивает идентичность объектов и почти всегда возвращает false. Сравнивай значения типа char.
Вызов strlen(s) в условии цикла в C. Функция повторно сканирует строку на каждом шаге, поэтому обработка 5 × 10^4 символов требует примерно 2.5 × 10^9 шагов.

Частые вопросы3

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

Пройдите по строке один раз, используя счётчик, который начинается с 0, и увеличивайте его на 1 каждый раз, когда текущий символ совпадает с нужным. Это займёт время O(n) и дополнительную память O(1). Для подсчёта без учёта регистра сначала переведите строку и букву в нижний регистр.

Можно ли использовать встроенную функцию подсчёта на собеседовании?

Обычно да, если ты можешь объяснить, сколько это стоит. str.count в Python и подобные функции всё равно просматривают всю строку, поэтому их сложность — O(n). Будь готов написать цикл, если интервьюер попросит.

Как бы ты посчитал все символы сразу?

Сделайте один проход и подсчитайте количество вхождений каждого символа в хеш-таблице или в массиве из 52 счётчиков для английских букв. После этого прохода количество вхождений любой буквы можно узнать за один поиск. Используйте этот способ, если вас спрашивают о многих буквах в одной и той же строке.

def countChar(s, c):
    # Напишите код здесь

Тест #1

Тест #2

Аргументы

s = "Mississippi"
c = "s"

Ожидаемый вывод