Count a Character

Q: Учитывается ли регистр символа при подсчёте?

В этой задаче — да: B и b — разные символы, поэтому в Banana нет b . Если вместо этого нужно подсчитать символы без учёта регистра, перед сравнением преобразуй и строку, и букву в нижний регистр.

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

+10

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

Функция

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 при отсчёте с 0, поэтому ответ — 4.

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

+18 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

Каждый символ s нужно проверить один раз, потому что любой из них может быть c. Это делается за один проход с помощью счётчика. Трудности обычно связаны с регистром (заглавная буква — это другой символ) и, в некоторых языках, со сравнением символа со строкой из одной буквы.

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

Идея

Создай копию s, удалив из неё все c. Каждый удалённый символ делает копию на один символ короче, поэтому разница между длинами двух строк в точности равна количеству вхождений c. В большинстве языков есть функция замены или удаления, которая выполняет это за тебя.

Для Mississippi и s копия будет такой: Miiippi. В ней 7 символов, а в исходной строке — 11, значит, c встречается 4 раза. Для Banana и b ничего не удаляется, потому что заглавная B не совпадает, и разница равна 0.

Нужно один раз пройти по s, поэтому время работы составляет O(n). Затраты связаны с памятью: копия может быть такой же длинной, как s, то есть требуется 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)

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

Идея

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

В слове Mississippi счётчик увеличивается на индексах 2, 3, 5 и 6 и в итоге равен 4. Каждый символ сравнивается один раз, и больше ничего не сохраняется.

Это даёт временную сложность O(n) и дополнительную сложность по памяти O(1): один счётчик и целевая буква. Улучшить время выполнения нельзя, потому что пропущенный символ мог бы оказаться ещё одной буквой 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.charAt(i) или s[i] — это один символ. Возьми c[0] (или c.charAt(0)) один раз до цикла.
Сравнение строк с помощью == в Java. Выражение String.valueOf(s.charAt(i)) == c сравнивает идентичность объектов и почти всегда возвращает false. Сравнивай значения типа char или используй equals.
Вызов strlen(s) в условии цикла в C. Эта функция проходит по всей строке на каждом шаге, поэтому обработка 5 × 10^4 символов требует около 2.5 × 10^9 шагов. Вместо этого останавливайся на терминаторе '\0'.

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

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

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

Учитывается ли регистр символа при подсчёте?

В этой задаче — да: B и b — разные символы, поэтому в Banana нет b. Если вместо этого нужно подсчитать символы без учёта регистра, перед сравнением преобразуй и строку, и букву в нижний регистр.

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

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

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Ввод

s = "Mississippi"
c = "s"

Ожидается