Problem D
Annorlunda Anagram
Languages
en
sv
Du får givet en sträng bestående av $N$ bokstäver, där $N$ är jämnt. Hitta ett sätt att kasta om bokstäverna i strängen så att samtliga $N/2+1$ delsträngar av längd $N/2$ blir olika.
Indata
En rad med en sträng $S$ av längd $N$ ($2 \leq N \leq 10^5$, $N$ är jämnt). Strängen innehåller bokstäver från “a” till “z”.
Utdata
Om det är möjligt att kasta om bokstäverna, skriv ut en sträng av samma längd som indatan, som är en omkastning av bokstäverna sådan att alla delsträngar av längd $N/2$ är olika. Om det är omöjligt, skriv ut $-1$.
Om det finns flera lösningar kan du skriva ut vilken som helst.
Förklaring av exempel
I det första exemplet är delsträngarna innan omkastning “tral”, “rala”, “alal”, “lala”, och “alal”. Här förekommer “alal” två gånger vilket inte är OK, däremot efter omkastning är alla delsträngarna olika.
I det tredje exemplet är alla delsträngar olika från början så det räcker med att skriva ut den ursprungliga strängen.
| Sample Input 1 | Sample Output 1 |
|---|---|
tralalal |
allatral |
| Sample Input 2 | Sample Output 2 |
|---|---|
zzzz |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
annorlunda |
annorlunda |
