Algorithm that given a word returns the minimum amount of letters needed to remove from it to become an anagram of a palindrome

I need a non-brute force algorithm for determining the minimum amount of letters you need to remove from a word for it to become an anagram of a palindrome.

For instance: abba -> 0, abbac -> 0, aabbfghj -> 3, a -> 0, abcdefghij -> 9.

Brute force algo can look like this:

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++

The brute force method is O(n*n!) complexity I believe (since for each word, there are n! anagrams, and n letters to remove). This will take way too long for strings n=1000 for example. So I need a better algorithm but am unsure of what I can check on the string to determine the amount of letters needed to remove.

Since all palindromes of n>1 have a pair/letter multiple somewhere (aba has pair aa, abcba pair aa and bb, aaab has aaa) I thought about removing all multiples of a letter then returning the length of the new word-1, or just the length if it's 0. This works for a lot of words, but it still fails for some. For example:

"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)

Am I missing something super simple here? How can I construct an algorithm that will return the minimum amount of letters you need to remove from a word to get an angram of a palindrome?

Solution

Am I missing something super simple here?

Yes you are :-)
Being an anagram of a palindrome can be characterized as follows:
a word w is an anagram of a palindrome if and only if, there exists at most one character c such that the number of occurences of c in w is odd (I let you see why that is true, test on simple cases).

So, given a word w, count for each character of w, the number of times it appears. Then count how many characters appear an odd number of times in w (let's call this k). The number of letters to remove so w can be the anagram of a palindrome is 0 if k=0 or if k=1. Otherwise it is k-1.