c++ - what's number anagram which are palindromes in string

Question

What is the number of anagrams which are palindromes in a string? Example : string = "aaabbbb"; Possible anagram's which are palindromes "abbabba" , "bbaaabb" and "bababab". The problem here is the time, i have string of size 10^9. here's my final code can anybody tell me what's the wrong with it ?

Answer 1

输入字符串中的每个字母都必须以偶数出现，除了一个字母可以以奇数出现。这封信在回文中的位置是固定的。它必须正好在中间。假设字母 a,b,c,... 的数量是 #a, #b, #c, ...

你只关心那些字母的一半，因为在回文中，后半部分是前半部分。所以我们只使用了一半的字母：

我使用了 floor 函数，所以我计算了以奇数出现的字母，正确。

那么前半部分有多少排列呢？这是一个不同排列的例子，所以我们得到

可能性。

---

对于您的示例： string = "aaabbbb";

我们得到：#a=3，#b=4。所以

我们得到 3 个回文，它们是 "abbabba" 、 "bbaaabb" 和 "bababab"，就像您发布的那样。

---

所以，如果你有一个非常大的字符串：

1. 计算每个字母的数量
2. 检查是否只有 1 个字母以奇数出现。它还有更多，你不能创建回文。
3. 使用公式计算不同回文的数量。

Answer 2

由于字谜的每一面都必须是另一边的镜像，所以我们关心的字谜的数量基本上只是我们可以在一侧形成的字谜的数量，所以：

1. 将字符串中的字符分组，使相同的字符组合在一起（例如，通过排序）。
2. 检查多个字符的奇数（因此，# anagrams = 0）。
3. 每组相同的字符取一半（奇数情况下截断）。
4. 计算这些字符的唯一排列数。