Разбор задачи «Анаграммы»

1. Идея

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

Это и есть проверка на анаграмму: если для каждой буквы от 'a' до 'z' число вхождений в s совпадает с числом вхождений в t, то ответ YES, иначе NO.

Удобно завести массив из 26 чисел:

• при просмотре строки s увеличивать счётчик соответствующей буквы;
• при просмотре строки t уменьшать счётчик.

Если после этого все значения равны нулю, строки подходят.

2. Наблюдения

Наблюдение 1

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

Например, abc и ab невозможно переставить друг в друга, потому что букв разное количество уже в целом.

Наблюдение 2

Так как строки состоят только из строчных латинских букв, возможных букв всего 26.

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

Наблюдение 3

Если для каждой буквы количество вхождений совпадает, то одна строка получается перестановкой другой.

Например:

• s = "abca"
• t = "caba"

Частоты одинаковы:

• a — 2 раза
• b — 1 раз
• c — 1 раз

Значит, ответ YES.

3. Алгоритм

1. Считать строки s и t.
2. Если len(s) != len(t), вывести NO.
3. Создать массив cnt из 26 нулей.
4. Для каждого символа c в s:
   • увеличить cnt[c - 'a'] на 1.
5. Для каждого символа c в t:
   • уменьшить cnt[c - 'a'] на 1.
6. Проверить все элементы массива cnt:
   • если хотя бы один не равен 0, вывести NO;
   • иначе вывести YES.

4. Почему это работает

Рассмотрим, что хранится в cnt[i].

Для буквы с номером i:

• сначала мы прибавили количество её вхождений в s,
• потом вычли количество её вхождений в t.

Итоговое значение равно разности:

число этой буквы в s - число этой буквы в t

Теперь возможны два случая.

Случай 1: все значения массива равны нулю

Тогда для каждой буквы количество вхождений в s и t одинаково. Значит, строки состоят из одинакового набора букв с одинаковыми кратностями, то есть являются анаграммами. Ответ YES.

Случай 2: есть хотя бы одно ненулевое значение

Тогда найдётся буква, которая встречается в одной строке чаще, чем в другой. Значит, строки не могут быть перестановками друг друга. Ответ NO.

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

Следовательно, алгоритм правильно определяет ответ.

5. Сложность

Пусть n = |s|, m = |t|.

• Проверка длин — O(1)
• Проход по строке s — O(n)
• Проход по строке t — O(m)
• Проверка массива из 26 элементов — O(26), то есть O(1)

Итоговая сложность: O(n + m)

Память:

• массив из 26 чисел

Итоговая память: O(1)

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

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

    vector<int> cnt(26, 0);

    for (char c : s) {
        cnt[c - 'a']++;
    }
    for (char c : t) {
        cnt[c - 'a']--;
    }

    for (int x : cnt) {
        if (x != 0) {
            cout << "NO\n";
            return 0;
        }
    }

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

7. Код на Python 3

s = input()
t = input()

if len(s) != len(t):
    print("NO")
else:
    cnt = [0] * 26

    for c in s:
        cnt[ord(c) - ord('a')] += 1
    for c in t:
        cnt[ord(c) - ord('a')] -= 1

    ok = True
    for x in cnt:
        if x != 0:
            ok = False
            break

    if ok:
        print("YES")
    else:
        print("NO")