Какая структура данных подходит для хранения количества букв в строках при проверке анаграмм

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

Выберете ли вы структуру под ограничения входа, а не по привычке. Первый уточняющий вопрос звучит так: «А если в строке не только латиница?» Следом просят оценить сложность и сравнить с сортировкой.

Как отвечать

Сначала уточните алфавит, от него зависит выбор:

• массив счётчиков: IntArray(26), если на входе только строчная латиница. Индекс это смещение символа от 'a', память постоянная, без объектов и боксинга;
• хэш-таблица: HashMap<Char, Int>, если символы любые. В Kotlin короткий вариант s.groupingBy { it }.eachCount(), а две такие карты сравниваются через ==.

Алгоритм с одним массивом: если длины разные, сразу false. Потом по первой строке увеличиваем счётчики, по второй уменьшаем, и если счётчик ушёл в минус, строки не анаграммы. Время O(n), память O(1) для фиксированного алфавита и O(k) для хэш-таблицы, где k это число разных символов. Сортировка обеих строк тоже работает, но за O(n log n) и с копированием в CharArray.

Для Android стоит упомянуть цену объектов. HashMap<Char, Int> хранит обёртки Character и Integer плюс узлы таблицы, это лишняя работа для сборщика мусора, если проверка крутится в цикле на главном потоке. Для целочисленных ключей в Android есть SparseIntArray, но здесь обычно хватает массива.

Отдельно про Unicode. Char в Kotlin это одна единица UTF-16, поэтому эмодзи занимают два Char, и считать их надо по кодовым точкам (codePoints()). Буква «й» может прийти одним символом или как «и» плюс знак краткой, поэтому перед подсчётом строки приводят к одной форме через java.text.Normalizer. Регистр и пробелы тоже решаются заранее: lowercase() и фильтр по isLetter().

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

Пишут IntArray(26) и индекс от 'a' без проверки входа. Первая же кириллическая буква даёт ArrayIndexOutOfBoundsException.

Пропускают проверку длины и не понимают, почему «abc» оказалась анаграммой «ab»: второй проход только уменьшает счётчики и лишний символ первой строки не замечает.

Заводят две карты и сравнивают их вложенными циклами, хотя хватает одной карты с плюсом и минусом или готового сравнения ==.