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

Чтобы добиться линейной сложности, нужно отказаться от сортировки.

Идея алгоритма

Определение:
Алгоритм подсчета символов сравнивает частоту каждого символа в двух строках.

Шаги алгоритма

Перед выполнением важно проверить длину строк.

Основные шаги:

1. Создать массив или Map счетчиков.

2. Пройти по первой строке и увеличить счетчики.

3. Пройти по второй строке и уменьшить счетчики.

4. Проверить, что все значения равны нулю.

Пример для ASCII

int[] freq = new int[256];

for (char c : s1.toCharArray()) {
    freq[c]++;
}
for (char c : s2.toCharArray()) {
    freq[c]--;
}

Если:

• все freq[i] == 0
  то строки — анаграммы.

Почему это O(n)

1. Каждый символ обрабатывается один раз.

2. Нет вложенных циклов.

3. Размер вспомогательной структуры фиксирован.

Краткий вывод

Подсчет символов позволяет проверить анаграммы за O(n), что делает этот алгоритм оптимальным по времени.