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

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

Умеете ли вы уйти от O(n²) к O(n) за счёт подсчёта частот и понимаете ли, что происходит с символами за пределами латиницы. Следом просят оценить память или спрашивают, что изменится для Unicode.

Как отвечать

Вложенные циклы, где для каждого символа первой строки ищется пара во второй, дают O(n²). Сортировка обеих строк через Arrays.sort и сравнение Arrays.equals уже O(n log n). Один проход тоже возможен:

• сравнить длины: разные длины сразу дают false;
• завести int[] count = new int[26] для строчной латиницы;
• в одном цикле по i увеличить счётчик для символа первой строки и уменьшить для символа второй, индекс считается как смещение символа от 'a';
• в конце убедиться, что все 26 счётчиков нулевые.

Финальная проверка тоже цикл, но по алфавиту фиксированного размера, это O(1), и на итоговую O(n) она не влияет. Если интервьюер настаивает на строго одном цикле, держите счётчик ненулевых ячеек: ячейка ушла из нуля, он растёт, вернулась в ноль, падает. После прохода строки анаграммы, если он равен нулю.

Про алфавит скажите заранее. Для произвольного текста массив на 26 не подходит: либо int[65536] по значению char, либо HashMap<Integer, Integer> с merge(cp, 1, Integer::sum). Причём charAt возвращает одну UTF-16 единицу, а эмодзи и часть иероглифов занимают две, поэтому корректный вариант идёт по codePoints().

Нормализацию тоже проговорите: регистр через toLowerCase(Locale.ROOT), пробелы и знаки препинания, если по условию «Dormitory» и «dirty room» считаются анаграммами.

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

Берут HashMap<Character, Integer> для латиницы. Работает, но с упаковкой каждого счётчика и заметно медленнее массива, и интервьюер обязательно спросит, зачем.

Считают индекс от 'a', не проверив входные данные. Заглавная буква или пробел дают отрицательный индекс и ArrayIndexOutOfBoundsException.

Забывают сравнить длины. В одном цикле по индексу первой строки хвост второй просто не прочитается, и «ab» с «abc» окажутся анаграммами.