Palindromic Transformations

This problem is adapted from PA 2022 Round Trial problem Palindrom.

Bytie, a member of the computer club, learned about palindromes — words that read the same forward and backward. For example, oko, kajak, kobyłamamałybok, and ababbaba are palindromes, while kajaki, zoo, alamakota, and abaababa are not.

Bytie quickly wrote down a word consisting only of the letters a and b. However, after a moment's reflection, he realized that the word might not be a palindrome. Thus, he decided to modify it. In one second, he can choose two adjacent letters and swap their positions.

Your task is to determine whether it is possible to transform the given string into a palindrome using a finite number of adjacent swaps (or even by doing nothing), and if so, compute the minimum number of seconds required.

Note: If it is impossible to form a palindrome, output -1.

Mathematical formulation: Given a string s of length n consisting of the letters a and b, determine the minimum number of adjacent swaps needed to transform s into a palindrome, or output -1 if no palindrome permutation exists. The correctness of the transformation relies on the necessary and sufficient condition that for a palindrome, at most one character has an odd frequency count. In LaTeX, this condition is given by: $$\#\{c:\, \text{count}(c)\ \text{is odd}\} \le 1.$$

inputFormat

The input consists of a single line containing the string s that comprises only the characters a and b.

outputFormat

Output a single integer: the minimum number of seconds (adjacent swaps) required to transform the input string into a palindrome. If it is impossible to form a palindrome, output -1.

sample

aba

0