Description

A palindrome is a string that reads the same forwards and backwards. For example, ABCBA is a palindrome, while ABCAB is not. Given any input string, you may repeatedly swap the $i$-th character with the $(i+1)$-th character to eventually make the string a palindrome. Find the minimum number of swaps.

Input Format

A string consisting of uppercase letters.

Output Format

If it can be transformed into a palindrome by a finite number of operations, output the minimum number of operations; otherwise output $-1$.

SHLLZSHZS

4

Hint

Sample Explanation:

1. Swap $\tt L$ and $\tt Z$ to get $\tt SHLZLSHZS$.
2. Swap $\tt L$ and $\tt Z$ to get $\tt SHZLLSHZS$.
3. Swap $\tt L$ and $\tt S$ to get $\tt SHZLSLHZS$.
4. Swap $\tt H$ and $\tt Z$ to get $\tt SHZLSLZHS$.

Constraints:

• For $40\%$ of the testdata, length $\leq50000$.
• For $100\%$ of the testdata, length $\leq10^6$.

Translated by ChatGPT 5