Как написать алгоритм удаления анаграмм из списка строк с линейной сложностью

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

Видите ли вы, что привычное решение с сортировкой символов каждой строки не линейное, и умеете ли построить ключ анаграммы за длину строки. Следом просят честно оценить сложность и спрашивают про Unicode.

Как отвечать

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

Для варианта «оставить первое вхождение»:

• ключ: вместо Arrays.sort по символам считаете частоты в int[26] и превращаете массив в строку. Сортировка стоит O(k log k) на слово, подсчёт O(k);
• проверка: HashSet<String> и метод add, который возвращает false, если ключ уже был. Отдельный contains не нужен;
• порядок: результат собираете в ArrayList по ходу обхода, исходный порядок сохраняется.

Set<String> seen = new HashSet<>();
List<String> result = new ArrayList<>();
for (String w : words) {
    int[] cnt = new int[26];
    for (char c : w.toCharArray()) cnt[c - 'a']++;
    if (seen.add(Arrays.toString(cnt))) result.add(w);
}

Сложность O(N), где N это суммарная длина всех строк: каждый символ читается один раз, ключ имеет постоянный размер. Операции HashSet в среднем O(1), а с Java 8 переполненные корзины HashMap превращаются в дерево, поэтому худший случай O(log n) на операцию.

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

Называют сортировку символов линейным решением. На коротких словах разница незаметна, но спрашивают именно про асимптотику.

Строят ключ как произведение простых чисел по буквам. На длинных словах long переполняется, и ключи разных слов начинают совпадать.

Молча считают, что алфавит только a..z. Заглавная буква, кириллица или пробел уронят cnt[c - 'a'] с ArrayIndexOutOfBoundsException. Для общего случая нужны частоты в Map<Integer, Integer> по codePoints(), сама карта годится ключом, потому что её equals сравнивает содержимое.