Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Спутниковые сети

Уровень: Новичок

📜 Уже третья находка

Во время раскопок на орбите Земли была обнаружена древняя система передачи данных — спутниковая сеть ранней цифровой эпохи.

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

Инженеры прошлого использовали простой, но гениальный принцип: если распределение символов в строке "сбалансировано", пакет считался корректным.

Ваша задача — расшифровать этот принцип и реализовать проверку корректности пакета.

🧠 Немного о технологии

В ранних спутниковых сетях данные передавались в виде строк символов. Однако из‑за космического излучения и помех отдельные символы могли искажаться.

Чтобы обнаруживать такие ошибки, инженеры анализировали частоту появления символов в контрольной строке.

Если распределение выглядело «подозрительно», пакет помечался как повреждённый.

📌 Частотный анализ

Речь идёт о методе проверки корректности строки по частотному анализу.

Для строки считается количество вхождений каждого символа.

Строка считается корректной, если выполняется одно из условий:

1. Все символы встречаются одинаковое количество раз.
2. Либо можно удалить ровно один символ из строки так, чтобы после этого частоты всех символов стали одинаковыми.

Такой подход позволяет обнаруживать единичные искажения данных.

⚙️ Алгоритм — как применяется на практике

На практике проверка выполняется следующим образом:

1. Подсчитать частоту каждого символа в строке.
2. Проанализировать распределение полученных частот.

3. Проверить:

   • одинаковы ли все частоты;
   • либо можно ли уменьшить одну из частот на 1 (удалив один символ), чтобы все значения стали равны.

Такой анализ используется не только в спутниковых системах, но и в:

• проверке целостности сообщений;
• анализе логов;
• системах обнаружения ошибок.

📌 Задача

Дана строка — контрольная строка спутникового пакета.

Необходимо определить, является ли пакет корректным.

Строка корректна, если:

• все символы встречаются одинаковое количество раз;
• или можно удалить ровно один символ так, чтобы частоты всех оставшихся символов стали одинаковыми.

Выведите результат проверки.

📥 Формат входных данных

Одна строка s, состоящая из строчных латинских букв.

Ограничения

• 1 ≤ |s| ≤ 10^5
• Строка содержит только символы от a до z

📤 Формат выходных данных

Выведите:

• YES, если пакет корректен;
• NO в противном случае.

📘 Примеры

Пример 1

Входные данные:

aabbcc

Выходные данные:

YES

Пояснение: каждый символ встречается по 2 раза.

Пример 2

Входные данные:

aabbccc

Выходные данные:

YES

Пояснение: если удалить один символ c, все частоты станут равны 2.

Пример 3

Входные данные:

aabbc

Выходные данные:

YES

Пояснение: если удалить символ c, оставшиеся символы встречаются по 2 раза.

Пример 4

Входные данные:

aabbcd

Выходные данные:

NO

Пояснение: невозможно удалить ровно один символ так, чтобы все частоты стали одинаковыми.