我们如何通过重新排列字符串中的字符来获得最大数量的回文子串？

Question

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

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

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

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

那么，再举两个例子：

if 字符串 -> oolol

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

if 字符串 -> gagadbcgghhchbdg

answer = abccbaghghghgdfd, 29 substrings can be formed

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

Answer 1

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

我们可以重新排列字符串以形成回文串 abc|cba，这将产生长度为 n 的回文子串（所有单个字符）+ n/2（通过反射点选择子串）+ {cases where在任一反射点都存在一个回文，在本例中为 0}。

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

同理，也可以构成3对回文(aba)(cbc)，此时回文的个数为n + n/3 + { .. }

显然，随着我们形成更多的 m 对回文，回文子串的数量将会下降。因此，我们需要考虑案例 I 和案例 II。在这两者中，通过增加同时出现的相等字符的密度，可以更好地最大化案例 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"))))

我们如何通过重新排列字符串中的字符来获得最大数量的回文子串？

How can we make maximum number of palindromic substrings by rearranging the characters in a string?

arrays

string

substring

dynamic-programming

palindrome