Уникальные слова по признаку анаграмм (оставить по одному представителю)

55. Оставить по одному представителю каждой группы анаграмм

Условие задачи:
Дана коллекция слов. Необходимо оставить по одному слову из каждой группы анаграмм.

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

Код:

class MyCode {

    public static void main(String[] args) {
        List<String> anagrams = List.of(
                "Race",
                "NIghT",
                "Angle",
                "CaRe",
                "angel",
                "ThiNG",
                "agnel",
                "angel"
        );

        System.out.println(removeAnagrams(anagrams));
    }

    public static List<String> removeAnagrams(
            List<String> anagrams
    ) {
        // код тут
    }
}

Ожидаемый результат:

[Race, NIghT, Angle]

Спойлеры к решению

Подсказки

💡 Для каждого слова построй канонический ключ.
💡 Приведи слово к нижнему регистру и отсортируй его символы.
💡 У всех анаграмм получится одинаковый ключ.
💡 Используй LinkedHashMap, чтобы сохранить порядок появления групп.
💡 Метод putIfAbsent() позволит оставить первое встретившееся слово.

Решение

public static List<String> removeAnagrams(
        List<String> words
) {
    if (words == null || words.isEmpty()) {
        return List.of();
    }

    Map<String, String> representatives =
            new LinkedHashMap<>();

    for (String word : words) {
        if (word == null) {
            continue;
        }

        String key = canonicalKey(word);
        representatives.putIfAbsent(key, word);
    }

    return new ArrayList<>(representatives.values());
}

private static String canonicalKey(String word) {
    char[] characters = word
            .toLowerCase(Locale.ROOT)
            .toCharArray();

    Arrays.sort(characters);

    return new String(characters);
}

Для слов Race и CaRe будет построен одинаковый ключ:

acer

Для слов Angle, angel и agnel ключом будет:

aegln

LinkedHashMap сохраняет порядок добавления ключей, а putIfAbsent() не заменяет первое сохранённое слово.

Временная сложность — O(n × L log L), где n — количество слов, а L — средняя длина слова. Дополнительная память — O(n × L).