Какой алгоритм использовать для сравнения строк на анаграммы

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

Умеете ли вы выбрать решение под ограничения и назвать его сложность, а не просто написать сортировку. Следом почти всегда спрашивают: а если алфавит не только латиница, а если слов миллион и их нужно сгруппировать по анаграммам.

Как отвечать

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

• сортировка: toCharArray(), Arrays.sort(), Arrays.equals(). Время O(n log n), память O(n) на массивы. Просто и надёжно, хороший первый ответ;
• подсчёт частот: массив int[26] для латиницы, по первой строке счётчик растёт, по второй уменьшается, в конце все нули. Время O(n), дополнительная память O(1). Для произвольного алфавита тот же приём на HashMap<Integer, Integer> с кодовой точкой в роли ключа.

Перед обоими проверка длины: разная длина сразу даёт false.

static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] cnt = new int[26];
    for (int i = 0; i < a.length(); i++) {
        cnt[a.charAt(i) - 'a']++;
        cnt[b.charAt(i) - 'a']--;
    }
    for (int c : cnt) if (c != 0) return false;
    return true;
}

Для группировки списка слов ключом служит отсортированная строка или строка из счётчиков, а слова собираются в Map<String, List<String>>.

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

Берут int[26] и не оговаривают ограничение. На кириллице charAt(i) - 'a' даст индекс за пределами массива и ArrayIndexOutOfBoundsException.

Забывают про регистр: «Listen» и «Silent» без toLowerCase(Locale.ROOT) не совпадут. Это лучше уточнить до кода, а не после замечания интервьюера.

Считают символы через char, хотя эмодзи и часть символов Unicode занимают две UTF-16 единицы. Для таких строк нужен codePoints(), иначе суррогатные пары считаются по половинкам и возможно ложное совпадение.