Как проверить анаграммы с алфавитом из 26 букв?

Условие

Даны две строки, состоящие только из строчных латинских букв a–z. Нужно определить, можно ли переставить буквы первой строки и получить вторую. Как использовать ограниченный алфавит, чтобы обойтись без сортировки?

Ответ

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

Для каждой буквы первой строки увеличьте счётчик с индексом код(буква) − код('a'), для второй — уменьшите. Например, для abca и caba все разности обнулятся; для abca и cbbb — нет. Время O(n+m), дополнительная память O(26), то есть O(1) при фиксированном алфавите. Ограничение a–z важно: для Unicode потребуется определить нормализацию и единицу сравнения, а массив из 26 элементов уже не подходит.