Question
Palindrome Trick II
You are given a string s of length n consisting only of lowercase English letters.
Your task is to rearrange the characters of s to form the lexicographically largest palindrome possible.
If it is not possible to rearrange the string into a palindrome, print -1.
Note:
→ A string is a palindrome if it reads the same forwards and backwards.
→ A string p is lexicographically larger than a string q if:
At the first position where they differ, the character in p comes later in the alphabet than the character in q.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains the string KaTeX can only parse string typed expression, consisting of KaTeX can only parse string typed expression lowercase English letters.
The second line contains the string KaTeX can only parse string typed expression, consisting of KaTeX can only parse string typed expression lowercase English letters.
Output
Print the lexicographically largest palindrome that can be formed by rearranging the letters of the string.
If no palindrome can be formed, print KaTeX can only parse string typed expression.
If no palindrome can be formed, print KaTeX can only parse string typed expression.
Example
Input
4
aabb
Output
baab
Explanation
We can rearrange "aabb" to "abba" or "baab".
Between the two, "baab" is lexicographically large.
Input
3
abc
Output
-1
Explanation
The string "abc" cannot be rearranged into a palindrome.
4
aabb
Output
baab
Explanation
We can rearrange "aabb" to "abba" or "baab".
Between the two, "baab" is lexicographically large.
Input
3
abc
Output
-1
Explanation
The string "abc" cannot be rearranged into a palindrome.