Частоты, группировка и подсчёт

Множество отвечает, какие значения встречались, но теряет кратность. Когда порядок не важен, а число повторений важно, состояние должно хранить частоту каждого ключа.

Что означает равенство строк с перестановкой

Даны две строки из символов ASCII. Нужно проверить, являются ли они анаграммами: можно ли переставить символы первой строки и получить вторую. Регистр и пробелы в этой версии считаются обычными различающимися символами.

Почему поиск с удалением становится квадратичным

Для каждого символа первой строки можно линейно искать совпадение во второй и удалять найденное. Поиск и удаление из середины строки стоят O(n), поэтому суммарно получается O(n²). Кроме того, изменяемая строка усложняет индексы.

Где повторно ищется оставшаяся кратность

Один и тот же остаток второй строки многократно просматривается ради ответа «сколько таких символов ещё осталось?». Это вопрос о частоте, а не о позиции.

Перестановка сохраняет частоты символов

Перестановка меняет порядок, но не меняет количество каждого символа. Анаграммы имеют одинаковую длину и одинаковую таблицу частот. Можно хранить одну таблицу баланса: прибавлять символы первой строки и вычитать символы второй.

Как читать таблицу баланса

После обработки первых i символов обеих строк balance[c] равен числу появлений c в префиксе первой строки минус число появлений в префиксе второй. После полного прохода строки являются анаграммами тогда и только тогда, когда все балансы равны нулю.

Прибавляем первую строку и вычитаем вторую

1. Если длины строк различаются, вернуть false.
2. Создать пустой словарь balance.
3. Для каждого символа первой строки увеличить его баланс.
4. Для каждого символа второй строки уменьшить его баланс.
5. Проверить, что каждое сохранённое значение равно нулю.

Проверка анаграмм одной таблицей

C++17

#include <cassert>
#include <string>
#include <unordered_map>

using namespace std;

bool areAnagrams(const string& first, const string& second) {
    if (first.size() != second.size()) {
        return false;
    }

    unordered_map<char, int> balance;
    for (char character : first) {
        ++balance[character];
    }
    for (char character : second) {
        --balance[character];
    }

    for (const auto& [character, count] : balance) {
        (void)character;
        if (count != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    assert(areAnagrams("listen", "silent"));
    assert(!areAnagrams("aab", "abb"));
    assert(!areAnagrams("ab", "a"));
    assert(areAnagrams("", ""));
}

Python 3

def are_anagrams(first: str, second: str) -> bool:
    if len(first) != len(second):
        return False

    balance: dict[str, int] = {}
    for character in first:
        balance[character] = balance.get(character, 0) + 1
    for character in second:
        balance[character] = balance.get(character, 0) - 1

    for count in balance.values():
        if count != 0:
            return False
    return True


assert are_anagrams("listen", "silent")
assert not are_anagrams("aab", "abb")
assert not are_anagrams("ab", "a")
assert are_anagrams("", "")

Цена частот и допущение об алфавите

При ожидаемом O(1) доступе к хеш-таблице время равно ожидаемому O(n), а память — O(k), где k — число различных символов. Здесь C++-строка рассматривается как последовательность байтов ASCII. Для произвольного Unicode её нельзя напрямую считать эквивалентом Python-строки без отдельной обработки кодировок.

Длина, регистр и повторяющиеся символы

• Разная длина сразу исключает анаграмму.
• Две пустые строки являются анаграммами.
• Одинаковый набор без одинаковой кратности, например aab и abb, не подходит.
• Регистр значим: A и a — разные ключи по текущему контракту.
• Пробелы и знаки пунктуации тоже считаются, если условие не требует нормализации.

Отличаем одинаковый набор от одинаковой кратности

Нужны переставленные строки listen/silent, ошибка кратности aab/abb, разные длины, пустые строки, повторяющиеся символы и пример с регистром. Если условие требует игнорировать пробелы, тест должен отдельно закрепить этап нормализации.

Когда порядок можно забыть, а повторы нельзя

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

Когда частоты теряют нужные позиции

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

Почему обычное множество даёт ложное равенство

Вопрос. Почему сравнение множеств символов ошибочно для aab и abb?

Ответ. Оба множества равны {a, b}, но частоты различаются: в первой строке две a, во второй — две b. Анаграмма требует равенства мультимножеств, а не обычных множеств.

Когда отрицательный баланс позволяет остановиться

Вопрос. Можно ли остановиться, как только при вычитании баланс стал отрицательным?

Ответ. Да, если первая таблица уже полностью построена: отрицательный баланс означает, что во второй строке символ встретился чаще, чем всего есть в первой, и будущие вычитания это не исправят.

Строим ключ для групп анаграмм

Сгруппируй список слов по анаграммам. Подсказка: для каждого слова построй неизменяемый ключ частот (например, кортеж из 26 счётчиков для строчных латинских букв) и добавь слово в список по этому ключу.

Самостоятельная задача о самом частом слове

Задача 1

Дан список слов в исходном порядке. Верните слово с наибольшим числом появлений; при равенстве выберите то, чьё первое появление было раньше. Пустой список должен давать явно описанный результат. Оцените время и память.

Частота хранит кратность, которую теряет множество

Когда порядок несущественен, но повторы важны, частотная таблица сохраняет ровно нужную информацию; баланс двух таблиц превращает сравнение анаграмм в один линейный проход.