Что такое анаграммы

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

Вопрос звучит как просьба дать определение, но настоящая цель это короткая задача на строки. Смотрят, выберете ли вы подсчёт символов вместо сортировки и вспомните ли про нормализацию входа.

Как отвечать

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

Способов два. Сортировка обеих строк и сравнение даёт O(n log n) и одну строку кода. Подсчёт даёт O(n) по времени и O(k) по памяти, где k это размер алфавита.

static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    Map<Integer, Integer> counts = new HashMap<>();
    a.codePoints().forEach(c -> counts.merge(c, 1, Integer::sum));
    for (int c : b.codePoints().toArray()) {
        Integer left = counts.get(c);
        if (left == null || left == 0) return false;
        counts.put(c, left - 1);
    }
    return true;
}

Проговорите допущения вслух: считаем ли регистр, пробелы и знаки препинания, один ли это алфавит. Если алфавит ограничен латиницей, массив счётчиков быстрее карты; для произвольного текста нужна карта по кодовым точкам.

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

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

Сравнивают посимвольно. В Java символ это единица UTF-16, и знаки вне базовой плоскости распадаются на суррогатную пару, поэтому посимвольный подсчёт на таких данных врёт. Надёжнее работать с кодовыми точками.

Молча решают за собеседника вопрос нормализации. Регистр, пробелы, дефисы и одинаковые на вид буквы разных алфавитов меняют ответ, и правильный ход это спросить, а не угадать. Отдельно стоит помнить, что приведение к нижнему регистру без явной локали ведёт себя по-разному в разных языках.

Ограничиваются сортировкой и не предлагают ничего лучше. Для длинных строк и для группировки тысяч слов лишний логарифм заметен, а собеседник ждёт именно перехода к линейному подсчёту.