Какой алгоритм подходит для проверки анаграмм за линейное время?

Question

Для линейного времени используется подсчет символов.
Алгоритм проходит по строкам один раз.
Используется массив или Map для частот.
Временная сложность O(n).
Это оптимальное решение задачи.

YeaHub · Accepted Answer

Чтобы добиться линейной сложности, нужно отказаться от сортировки.Идея алгоритмаОпределение:Алгоритм подсчета символов сравнивает частоту каждого символа в двух строках.Шаги алгоритмаПеред выполнением важно проверить длину строк.Основные шаги:Создать массив или Map счетчиков.Пройти по первой строке и увеличить счетчики.Пройти по второй строке и уменьшить счетчики.Проверить, что все значения равны нулю.Пример для ASCIIint[] freq = new int[256];

for (char c : s1.toCharArray()) {
    freq[c]++;
}
for (char c : s2.toCharArray()) {
    freq[c]--;
}
Если:все freq[i] == 0то строки — анаграммы.Почему это O(n)Каждый символ обрабатывается один раз.Нет вложенных циклов.Размер вспомогательной структуры фиксирован.Краткий выводПодсчет символов позволяет проверить анаграммы за O(n), что делает этот алгоритм оптимальным по времени.