SJSU Weekly Practice Problems 1/2

Start

2022-01-02 20:00 AKST

SJSU Weekly Practice Problems 1/2

End

2022-01-09 20:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -139 days 21:14:09

Time elapsed

168:00:00

Time remaining

0:00:00

Problem P
Alternative Anagram

Consider a string of $N$ letters, where $N$ is an even number. Rearrange the letters such that all $N/2+1$ substrings of length $N/2$ are different.

Input

A single line containing string $S$ of length $N$, where $2 \leq N \leq 10^5$ and $N$ is even. The string consists of lower-case letters from the English alphabet, “a” to “z”.

Output

If possible, print a string of length $N$ that is a rearrangement of the letters in $S$ such that all substrings of length $N/2$ are different. If this is impossible, print $-1$.

If there is more than one solution, any one will do.

Explanation of Sample Inputs

In the first example, the substrings before rearrangement are “tral”, “rala”, “alal”, “lala”, and “alal”. Note that “alal” appears twice. After the rearrangement, all substrings are different.

In the third example, all substrings are different already in the input, so it suffices to print the original string.

Sample Input 1 Sample Output 1
tralalal
allatral
Sample Input 2 Sample Output 2
zzzz
-1
Sample Input 3 Sample Output 3
annorlunda
annorlunda