Можно ли использовать сортировку и сравнение отсортированных массивов символов для проверки анаграмм

Что проверяют

Умеете ли вы оценить простое решение: сложность, память, граничные случаи. Почти всегда следом просят сделать быстрее, то есть перейти к подсчёту частот за O(n).

Как отвечать

Да, это корректный и самый короткий способ: строки являются анаграммами тогда и только тогда, когда совпадают их отсортированные символы. Каркас на Java: сначала сравнить длины, затем toCharArray() для обеих строк, Arrays.sort() для каждого массива и Arrays.equals() для сравнения.

Оценка: O(n log n) по времени из-за сортировки и O(n) дополнительной памяти, потому что toCharArray() всегда создаёт копию. Проверка длины в начале отсекает очевидные несовпадения за O(1).

Альтернатива за O(n): массив счётчиков. Для строчной латиницы хватит int[26], для произвольного текста подойдёт HashMap<Integer, Integer> по кодовым точкам. По первой строке счётчики увеличиваете, по второй уменьшаете, в конце все должны быть нулями.

Дальше уточните правила у интервьюера, это отдельный плюс:

• регистр: приводите через toLowerCase(Locale.ROOT), иначе «Listen» и «silent» не совпадут;
• пробелы и знаки: для фраз их обычно отбрасывают, например replaceAll("[^\\p{L}]", "");
• Unicode: char это кодовая единица UTF-16, эмодзи занимает две, и сортировка разорвёт суррогатную пару. Надёжнее s.codePoints().sorted().toArray(), а составные буквы вроде «й» перед этим приводить к одной форме через Normalizer.normalize(s, Normalizer.Form.NFC).

Где спотыкаются

Сравнивают массивы через == или x.equals(y). Это сравнение ссылок, результат будет false даже для настоящих анаграмм, нужен Arrays.equals.

Называют решение с сортировкой линейным. Сортировка сравнением даёт O(n log n), и следующий вопрос интервьюера будет именно об этом.

Делают счётчик int[26] с индексом c - 'a' и не проверяют входные данные. На заглавной букве или кириллице это ArrayIndexOutOfBoundsException, поэтому либо нормализуйте вход, либо берите структуру пошире.