找到给定字符串的字典序最小回文串

Question

我需要找到字典序最小的回文字符串。比如说，

s = "axxb??"

这两个问号可以分别替换成字符 a 和 b，这样就可以形成一个字符串

s ="axbab" 

然后这个字符串可以重新排列成 "abxxba"，这是通过插入字符串得到的字典序最小的回文字符串。

这个方法在

string='a?rt???' 

上有效，输出结果是 'aartraa'。在这里，问号可以替换成 'a','r','a' 和 'a' 来形成回文。但是当我尝试另一个例子时，

string='ai?a??u'

我得到了'无法形成回文'的结果。下面是我尝试的代码。

def find_smallest_palindrome(s):
    s = list(s)
    n = len(s)
    i, j = 0, n - 1

    while i < j:
        if s[i] == "?" and s[j] == "?":
            s[i] = "a"
            s[j] = "a"
        elif s[i] == "?":
            s[i] = s[j]
        elif s[j] == "?":
            s[j] = s[i]
        elif s[i] != s[j]:
            return "Palindrome not possible"

        i += 1
        j -= 1

    return "".join(s)


s = "ai?a??u"
candidate = find_smallest_palindrome(s)

if candidate == "Palindrome not possible":
    print("Palindrome not possible")
else:
    print(candidate)

Answer 1

我觉得你可能没有看到更重要的事情。也就是说：

• 一个字符串的字母可以重新排列成回文，前提是：要么字符串的长度是偶数，并且每个字母出现的次数都是偶数，要么字符串的长度是奇数，只有一个字母出现的次数是奇数，其余的字母出现的次数都是偶数。

• 如果你有一个符合以上条件的字符串，能组成的最小的字母重排（也就是字母的排列）是：先取字母表中最小的字母的一半（如果需要的话向下取整），然后是字母表中第二小的字母的一半……中间放一个出现次数为奇数的字母（如果总长度是奇数的话），最后再把剩下的字母反向排列。

所以

1. 先统计每个字母的出现次数，还要统计“？”的数量。

2. 如果你的总长度是偶数，就给每个出现次数为奇数的字母分配一个“？”；如果总长度是奇数，就给每个出现次数为奇数的字母分配一个“？”，但最大的字母除外。如果“？”不够用，那就没戏了，无法形成回文。

3. 剩下的“？”数量应该是偶数（可能是0）。把它们都变成“a”或者你所能用的最小的字母。

4. 按照上面描述的方法形成一个回文。