Подсчёт различных символов
Количество различных символов в строке — это число символов, которые встречаются в ней хотя бы один раз. Повторные вхождения одного и того же символа считаются только один раз.
Как считать
Удобный способ — просмотреть строку слева направо и поддерживать множество уже встреченных символов. Если текущего символа в множестве ещё нет, его добавляют и увеличивают счётчик. Если символ уже встречался, счётчик не изменяют. Такой подсчёт является основой частоты символов, но отвечает на другой вопрос: не сколько раз встретился каждый символ, а сколько разных символов встретилось всего.
Здесь \(s_i\) — символ строки на позиции \(i\), \(n\) — длина строки, а \(D\) — количество различных символов. Всегда выполняется \(0 \le D \le n\). Если строка непустая и состоит только из одинаковых символов, то \(D=1\).
В строке банан символы по порядку: б, а, н, а, н. Разные символы — б, а, н, поэтому количество различных символов равно \(3\). Таблица, в которой для каждого символа хранится число его появлений, называется таблицей частот символов.
Длина строки учитывает все символы, включая повторы. Например, длина строки банан равна \(5\), а количество различных символов — \(3\). Также не следует путать эту величину с проверкой вхождения символа, которая даёт ответ только для одного выбранного символа.
Сколько различных символов в строке абракадабра?
а, б, р, к, д — всего пять разных символов.д или один из других разных символов.Главное
- Различный символ учитывается один раз, независимо от числа его повторений.
- Количество разных символов равно размеру множества символов строки: \(D = |\{s_i\}|\).
- Не путайте количество различных символов с длиной строки и с частотой отдельного символа.