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

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 的所有回文在某处都有一个 pair/letter 倍数（aba 有对 aa、abcba 对 aa 和 bb, aaab 有 aaa) 我考虑删除一个字母的所有倍数，然后 return 计算新单词的长度 - 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)

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

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.

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

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

algorithm

palindrome

anagram