200882: [AtCoder]ARC088 E - Papple Sort
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $800$ points
Problem Statement
You are given a string $S$ consisting of lowercase English letters. Determine whether we can turn $S$ into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.
Constraints
- $1 \leq |S| \leq 2 × 10^5$
- $S$ consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
$S$
Output
If we cannot turn $S$ into a palindrome, print -1
. Otherwise, print the minimum required number of operations.
Sample Input 1
eel
Sample Output 1
1
We can turn $S$ into a palindrome by the following operation:
- Swap the $2$-nd and $3$-rd characters. $S$ is now
ele
.
Sample Input 2
ataatmma
Sample Output 2
4
We can turn $S$ into a palindrome by the following operation:
- Swap the $5$-th and $6$-th characters. $S$ is now
ataamtma
. - Swap the $4$-th and $5$-th characters. $S$ is now
atamatma
. - Swap the $3$-rd and $4$-th characters. $S$ is now
atmaatma
. - Swap the $2$-nd and $3$-rd characters. $S$ is now
amtaatma
.
Sample Input 3
snuke
Sample Output 3
-1
We cannot turn $S$ into a palindrome.