我们如何通过重新排列字符串中的字符来制作最大数量的回文子字符串?

Question

一个字符串被称为另一个字符串的子字符串，如果可以通过从它的开头和结尾删除一些(可能是零(个字符来从该字符串中获取它。

例如，abc、ab和c是字符串abc的子字符串，而ac和d则不是。

让我们将字符串的回文计数定义为回文的子字符串的数量。

例如，字符串aaa的回文计数为 6，因为它的所有子字符串都是回文。字符串abc的回文计数为 3，因为只有其长度为 1 的子字符串是回文。

所以，还有两个例子：

1. 如果字符串 ->oolol

   answer = ololo,  9 substrings can be formed
   'o', 'l', 'o', 'l', 'o', 'olo', 'lol', 'olo', 'ololo'
   

2. 如果字符串 ->gagadbcgghhchbdg

   answer = abccbaghghghgdfd, 29 substrings can be formed
   

你会得到一个字符串 s。您可以任意重新排列其字符。您的目标是获得具有回文计数最大可能值的字符串。

Answer 1

产生最大回文数的字符串的最佳可能重新排列可能是sorted string。以字符串abcabc为例，让n表示字符串的大小。

我们可以重新排列字符串以形成回文abc|cba，这将产生长度为 n(所有单个字符(+ n/2(在反射点上拾取子字符串(+ {在任一反射点存在回文的情况，在本例中为 0}。

我们还可以重新排列字符串以形成形式为(aa)(bb)(cc)的回文对，这将产生 n(单字符(+ n/2(成对子字符串(+ {其他可能的回文子字符串} 回文。

类似地，一个3对回文也可以形成(aba)(cbc)，在这种情况下回文的数量将是n + n/3 + {.. }

显然，当我们形成更多的m对回文结构时，回文子弦的数量将会下降。因此，我们需要考虑案例一和案例二。在两者中，通过增加一起出现的相等字符的密度，可以更好地最大化情况 II 的 {other ..} 大小写，这是排序字符串中的情况。因此，排序字符串应产生最佳答案。

因此，对于您的情况oolol->llooo将给出 9 的最佳结果，gagadbcgghhchbdg->aabbccddfgggghhh也将给出 29 的最佳结果。您可以使用以下代码检查任何字符串：https://ideone.com/mMu2tq

def ispalin(s):
return (s == s[::-1])
def cpalin(s):
c = 0
for i in range(len(s)):
for j in range(i, len(s)):
if ispalin(s[i:j + 1]):
c += 1
return c
print(cpalin(''.join(sorted("abccbaghghghgdfd"))))
print(cpalin(''.join(sorted("oolol"))))