Palindrome Reorder

Task:

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).

Input

The only input line has a string of length $n$ consisting of characters A–Z.

Output

Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".

Constraints

• $1 \le n \le 10^6$
  

Solutions:

Paladindrome is a symmetrical string. It means the count of each character is either all even or at most one odd. Hence, firstly counting the characters and then checking whether it satisfy above conditions. If existing valid Paladindrome, forming it.

 1def solve(string):
 2    tracking=[0]*26
 3    for i in string:
 4        tracking[ord(i)-65]+=1
 5    # Quantity of characters whose count is odd.
 6    count_odd=0
 7    # Result
 8    res=""
 9    # Paladindrome for character whose count is odd.
10    odd_character=""
11    for i in range(len(tracking)):
12        if tracking[i]!=0:
13            if tracking[i]&1==1:
14                count_odd+=1
15                odd_character=chr(i+65)*tracking[i]
16            else:
17                res+=chr(i+65)*(tracking[i]//2)
18    # If having more than 1. Then returning NO SOLUTION.
19    if count_odd>1:
20        return "NO SOLUTION"
21    # Otherwise, forming and returning Paladindrome.
22    else:
23        return res+odd_character+res[::-1]
24string=input().strip()
25print(solve(string))
26 

Time complexity: We firstly go through the string to get the counter, then iterating this counter which has fixed length (26). Time complexity will be $O(N+26)$. Concise form: $O(N)$.

Space complexity: Even though using additional array for holding the counter, but it's fixed. Space complexity: $O(1)$.