Разбор задачи «Проверка корректности пакета»

Идея задачи

Дана строка s, состоящая из строчных латинских букв. Нужно определить, можно ли считать её корректной.

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

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

Что именно нужно проверить

Нас интересуют не сами символы, а частоты их вхождения.

Например:

• aabbcc → частоты: 2, 2, 2
• aabbccc → частоты: 2, 2, 3
• aabbc → частоты: 2, 2, 1
• aabbcd → частоты: 2, 2, 1, 1

Нужно понять, когда такие частоты можно привести к одному значению удалением одного символа.

Ключевое наблюдение

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

После этого удобно посмотреть не только на сами частоты, но и на то, сколько букв имеют каждую частоту.

Например:

• для строки aabbccc
  • частоты букв: 2, 2, 3
  • значит:
    • частота 2 встречается у двух букв;
    • частота 3 встречается у одной буквы.

То есть мы можем хранить структуру вида:

• freqCount[частота] = сколько букв имеют такую частоту

Это позволяет быстро понять, возможна ли корректировка удалением одного символа.

Какие случаи дают ответ YES

Случай 1. Все частоты уже одинаковы

Если все буквы встречаются одинаковое количество раз, то строка уже корректна.

Пример:

• aabbcc → 2, 2, 2

Тогда сразу выводим YES.

Случай 2. Есть ровно две разные частоты

Пусть есть только две разные частоты:

• меньшая f1, она встречается c1 раз;
• большая f2, она встречается c2 раз.

Тогда строку можно исправить только в двух подслучаях.

Подслучай 2.1. Одна буква встречается ровно один раз

Если:

• f1 = 1
• и такая частота встречается ровно у одной буквы (c1 = 1),

то мы можем удалить эту единственную букву целиком.

Пример:

• aabbc → частоты 2, 2, 1
• удаляем c
• получаем 2, 2

Ответ: YES.

Подслучай 2.2. Одна буква встречается на 1 раз больше остальных

Если:

• f2 = f1 + 1
• и большая частота встречается ровно у одной буквы (c2 = 1),

то можно удалить один символ у этой буквы и выровнять частоты.

Пример:

• aabbccc → частоты 2, 2, 3
• удаляем один c
• получаем 2, 2, 2

Ответ: YES.

Когда ответ NO

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

Пример:

• aabbcd → частоты 2, 2, 1, 1

Здесь после удаления одного символа всё равно останутся разные частоты, поэтому ответ NO.

Почему других случаев быть не может

Удаление одного символа меняет только одну букву:

• либо её частота уменьшается на 1;
• либо, если частота была 1, эта буква вообще исчезает.

Значит, после одного удаления мы можем исправить только одну «проблемную» частоту.

Если разных частот больше двух, то одним удалением привести всё к равенству невозможно.

Если разных частот ровно две, то остаются только два рабочих варианта:

1. убрать букву, которая встречается один раз;
2. уменьшить на единицу частоту одной «лишней» буквы.

Это и даёт полный критерий.

Алгоритм

1. Считаем частоты всех букв строки.
2. Убираем нулевые частоты.
3. Считаем, сколько раз встречается каждая частота.
4. Проверяем:
   • если различных частот одна → YES;
   • если различных частот не две → NO;
   • иначе проверяем два специальных случая:
     • меньшая частота равна 1 и встречается один раз;
     • большая частота на 1 больше меньшей и встречается один раз.

Оценка сложности

Пусть длина строки равна n.

• Подсчёт частот букв: O(n)
• Остальная обработка: O(1), потому что букв всего 26

Итоговая сложность:

• Время: O(n)
• Память: O(1)

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<int> cnt(26, 0);
    for (char c : s) {
        cnt[c - 'a']++;
    }

    unordered_map<int, int> freqCount;
    for (int x : cnt) {
        if (x > 0) {
            freqCount[x]++;
        }
    }

    if (freqCount.size() == 1) {
        cout << "YES\n";
        return 0;
    }

    if (freqCount.size() != 2) {
        cout << "NO\n";
        return 0;
    }

    auto it = freqCount.begin();
    int f1 = it->first;
    int c1 = it->second;
    ++it;
    int f2 = it->first;
    int c2 = it->second;

    if (f1 > f2) {
        swap(f1, f2);
        swap(c1, c2);
    }

    if (f1 == 1 && c1 == 1) {
        cout << "YES\n";
        return 0;
    }

    if (f2 == f1 + 1 && c2 == 1) {
        cout << "YES\n";
        return 0;
    }

    cout << "NO\n";
    return 0;
}

Реализация на Python

from collections import Counter

s = input().strip()

letter_count = Counter(s)
freq_count = Counter(letter_count.values())

if len(freq_count) == 1:
    print("YES")
elif len(freq_count) == 2:
    (f1, c1), (f2, c2) = freq_count.items()

    if f1 > f2:
        f1, f2 = f2, f1
        c1, c2 = c2, c1

    if f1 == 1 and c1 == 1:
        print("YES")
    elif f2 == f1 + 1 and c2 == 1:
        print("YES")
    else:
        print("NO")
else:
    print("NO")

Пояснение на примерах

Пример 1

Строка:

aabbcc

Частоты:

2, 2, 2

Все одинаковы, значит ответ YES.

Пример 2

Строка:

aabbccc

Частоты:

2, 2, 3

Есть одна буква с частотой на 1 больше остальных. Удаляем один символ c, получаем 2, 2, 2.

Ответ YES.

Пример 3

Строка:

aabbc

Частоты:

2, 2, 1

Есть одна буква, которая встречается ровно один раз. Удаляем её полностью.

Ответ YES.

Пример 4

Строка:

aabbcd

Частоты:

2, 2, 1, 1

Одним удалением привести все частоты к одному значению нельзя.

Ответ NO.

Частые ошибки

1. Проверять только сами частоты, но не количество букв с такой частотой

Важно не только знать, какие частоты есть, но и сколько раз каждая из них встречается.

Например, строки с частотами:

• 2, 2, 3 — исправимы;
• 2, 3, 3 — уже нет.

2. Забыть про случай, когда одна буква встречается один раз

Строка aabbc должна давать YES, потому что можно удалить c полностью.

3. Считать, что двух разных частот всегда достаточно

Это не так. Например:

• 1, 1, 2, 2 — две разные частоты есть,
• но сделать все равными одним удалением нельзя.