Rohan calls a string almost pallindrome if it can be separated into two halves such that each half is permutation of one another. But if length of string is odd then you can divide the string into two half, and there will be only one extra character that will be the middle character
For example : "radar" is an almost pallindrome because two halves are "ra" and "ar" are permutations of each other and d is extra character which is in the middle of the string.
Given a string X you have to count total adjacent swaps required to convert that string to almost pallindrome . If it is not possible , simply print -1 as output.
Examples / Hints
ramaaamr : This is almost pallindrome as it can be divided into rama and aamr and amar is permutation of aamr or vice versa. So total swaps required are 0
raonraons : This is not almost pallindrome as it can't be divided into two halves such that they are permutation of each other but if we swap s with 4 characters towards left then it would become raonsraon whcih is an almost pallindrome. So total swaps required are 4
First line contains a string as input
Output total adjacent swaps required to make the string almost pallindrome
1≤ |String| ≤ 10^6+5
If you swap d with two characters on the left then string formed is "radra" which is almost pallindrome