Canonical Palindrome

Difficulty: 1300 3000 ms 128 MB

strings

Rearrange the characters of S into a palindrome, or print NO SOLUTION. To make the answer unique, output the palindrome whose first half is SORTED alphabetically (the odd-count character, if any, goes in the middle).

Input: one line with a lowercase string.

Output: the canonical palindrome, or NO SOLUTION.

Constraints:

• 1 ≤ |S| ≤ 10⁵

Sample Tests

aabbc

abcba

aabbcd

NO SOLUTION

Read the Editorial