Palindrome Reorder

Explanation

Here, we are given a string and we need to reorder it in such a way that it becomes a palindrome if possible, otherwise print NO SOLUTION.

Now, in a palindrome, all the characters except at most one must have even frequency. So, we can count the frequency of each character and then check if there is more than one character with odd frequency. If there is, then we can't make a palindrome, otherwise we can.

If it is possible to make a palindrome, then we'll first print all the characters with even frequency half the times in any order. Then, print all the characters with odd frequency. Then, print all the characters with even frequency half the times in reverse order.

Code

from collections import defaultdict

s = input()

freqs = defaultdict(lambda: 0)
for ch in s:
    freqs[ch] += 1

odd_count = 0
for freq in freqs.values():
    if freq % 2 == 1:
        odd_count += 1

if odd_count <= 1:
    start = ""
    mid = ""
    for ch, freq in freqs.items():
        if freq % 2 == 1:
            mid = ch * freq
        else:
            start += ch * (freq // 2)
    print(start + mid + start[::-1])
else:
    print("NO SOLUTION")