P5041 [HAOI2009] Make a Palindrome

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.

A string consisting of uppercase letters.

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

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