Можно ли получить палиндром перестановкой символов строки

Условие

Дана строка S. Нужно определить, можно ли переставить её символы так, чтобы образовалась строка‑палиндром. Функция должна вернуть true, если такое расположение символов существует, и false в противном случае.

public boolean canFormPalindrome(String input) {
    // ...
}

Ответ

Перестановка в палиндром возможна, если не более одного символа встречается нечётное число раз. Такой символ занимает центр; остальные разбиваются на зеркальные пары.

public boolean canFormPalindrome(String input) {
    java.util.Objects.requireNonNull(input);
    java.util.Set<Integer> odd = new java.util.HashSet<>();
    input.codePoints().forEach(c -> {
        if (!odd.add(c)) odd.remove(c);
    });
    return odd.size() <= 1;
}

Регистр, пробелы и пунктуация здесь значимы. Используются Unicode code points, не UTF-16 половинки суррогатных пар. Пустая строка даёт true. Ожидаемое время O(n), память O(k) по числу разных символов; сам палиндром строить не требуется.