Алгоритм, который дает слово возвращает минимальное количество букв, необходимое для удаления из него, чтобы стать анаграммой палиндрома

Question

Мне нужен алгоритм не грубой силы, чтобы определить минимальное количество букв, которое нужно удалить из слова, чтобы оно стало анаграммой палиндрома.

Например: abba -> 0, abbac -> 0, aabbfghj -> 3, a -> 0, abcdefghij -> 9.

Алгоритм грубой силы может выглядеть так:

1. Send word to method (2.) with counter 0
2. Check if any anagrams of word is palindrome, if yes return counter, if no go to 3.
3. Remove head of word, send to method (2.) with counter++

Метод грубой силы - сложность O (n * n!), Я считаю (поскольку для каждого слова есть n! Анаграмм и n букв для удаления). Например, это займет слишком много времени для строк n = 1000. Поэтому мне нужен лучший алгоритм, но я не уверен, что я могу проверить строку, чтобы определить количество букв, которое нужно удалить.

Поскольку все палиндромы с n> 1 где-то имеют пару / букву, кратную (aba имеет пару aa, abcba пара aa и bb, aaab имеет aaa), я подумал о удаление всех кратных букв, а затем возвращение длины нового слова-1 или только длины, если оно равно 0. Это работает для многих слов, но для некоторых все равно не получается. Например:

"aabbfghj" (remove pairs) -> "fghj" (length >0) -> return length-1 = 3 correct
"aabbcc" -> "" (!length >0) -> return length = 0 correct
"aaabb" -> "" -> 0 correct
"aaabbb" -> "" -> 0 correct
"aaabbbccdef" -> "def" -> 2 correct
"aaaaab" -> "b" -> 0 correct
"aabbc" -> "c" -> 0 correct
"aaabbc" -> "c" -> 0 incorrect (should be 1)

Я что-то упустил здесь очень просто? Как я могу построить алгоритм, который будет возвращать минимальное количество букв, которое нужно удалить из слова, чтобы получить анграмму палиндрома?

Answer 1

Я что-то упускаю здесь очень просто?

Да, вы: -)
Быть анаграммой палиндрома можно охарактеризовать следующим образом:
слово w является анаграммой палиндрома в том и только в том случае, если существует не более одного символа c, такого, что число вхождений c в w является нечетным (я позволю вам понять, почему это так, проверьтепростые случаи).

Итак, учитывая слово w, подсчитайте для каждого символа w, сколько раз оно встречается.Затем посчитайте, сколько символов появляется нечетное количество раз в w (назовем это k).Число букв, которые нужно удалить, поэтому w может быть анаграммой палиндрома: 0, если k=0 или k=1.В противном случае это k-1.