Find lexicographically smallest palindrome for a given string

Question

I need to find Lexicographically smallest palindrome.For example,

s = "axxb??"

the two question marks can be replaced with the characters a and b respectively to form a string

s ="axbab" 

and the string can be rearranged to "abxxba" which is the lexicographically smallest palindrome possible by interpolating the string.

It worked for

string='a?rt???' 

and gave me output as 'aartraa'. Here question marks can be replaced with 'a','r','a' and 'a' to form the palindrome. but when I tried for another

string='ai?a??u'

I'm getting 'palindrome not possible'. Below is the code I tried.

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

I think you're missing the bigger picture. Namely:

• The letters of a string can be rearranged to form a palindrome if either (a) the length of the string is even and every letter occurs an even number of times, or (b) the length of the string is odd and every letter except one occurs an even number of times.

• Given a string that fits the above criteria, the smallest anagram that can be made from the letter has you taking half (rounding down, if necessary) the smallest letter alphabetically followed by half the next smallest letter alphabetically, ... followed by a single occurrence of the letter with the odd count [if the total lenghth is odd] in the middle followed by everything in reverse order.

So

1. Get a count of each letter, and also count the "?"s.

2. If your total length is even, assign one "?" to each of the letters with an odd count. If your total length is odd, assign one "?" to each of the letters with an odd count, except for the largest letter alphabetically. If you don't have enough "?"s, you're out of luck and can't form a palindrome.

3. You'll have an even number of "?"s (possibly 0) remaining. Make them all be "a"s, or whatever is your smallest legal letter.

4. Form a palindrome as described above.