给定单词的算法返回从单词中删除以成为回文字母的最小字母

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具有对/字母倍数（具有pair aa，abcbapair aa和bb，aaabhas 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，使得cin 的出现数w是奇数（我让您会明白为什么这样做是对的，请测试一些简单的案例）。

因此，给定一个单词w，对的每个字符计数，w它出现的次数。然后计算有多少个字符出现奇数次w（我们称之为k）。要删除的字母数w可以是回文的字谜是0if k=0或if k=1。否则是k-1。