给定一个单词的算法返回从中删除成为回文字谜所需的最少字母数

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)

我是不是漏掉了一些 super 简单的东西？我如何构建一种算法，该算法将返回您需要从单词中删除的最少字母数量才能获得回文字谜？

Answer 1

Am I missing something super simple here?

是的，你是:-)
作为回文的变位词可以表征如下:
一个单词 w 是回文的变位词当且仅当，最多存在一个字符 c 使得 c 的出现次数在 w 中是奇怪的(我让你明白为什么这是真的，在简单的情况下测试)。

因此，给定一个单词 w，计算 w 的每个字符出现的次数。然后计算有多少个字符在 w 中出现奇数次(我们称之为 k)。如果 k=0 或 k=1，则要删除的字母数 w 可以是回文的变位词是 0 。否则为k-1。