You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.

## HackerEarth - Shil, and Palindrome Solution

Beeze Aal

Shil is your new boss and he likes palindromes very much. Palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. (ex. madam , aabaa, racecar)

Given a string S , beautiful Palindrome is a lexicographical minimum palindrome that can be formed by rearranging all the characters of string S. In order to please your boss, find a beautiful Palindrome that can be formed with help of string S.

String x is lexicographically less than string y, if either x is a prefix of y (and xββ βy), or there exists such i (1ββ€βiββ€βmin(|x|,β|y|)), that xiβ<βyi, and for any j (1ββ€βjβ<βi) xjβ=βyj. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languagesββ.

Input:
Only line of input contains string S. All the letters of this string will be in lower letters('a' - 'z').

Output:
Output lexicographical minimum Palindrome that can be formed by rearranging all the letters of string S. If no such Palindrome exist for given input, print -1.

Constraints:
1β€|S|β€100000

SAMPLE INPUT

aabcc 

SAMPLE OUTPUT

acbca 

Explanation

After rearranging all the characters , all the palindromes that can be formed are cabac and acbca. Out of these two lexicographical minimum one is acbca.

### Solution in Python

import sys
from collections import Counter
s = input().strip()
c = Counter(s)
pal = ""
mid = ""
odd = 0

for k,v in c.items():
if v%2:
odd+=1
mid+=k
v-=1
pal+=k*(v//2)

if odd > 1 :
print("-1")
else:
pal = "".join(sorted(pal))
print(pal+mid+pal[::-1])