Hi, beautiful people of Codeforces!

I've been stuck on this problem for quite a long time: https://stackoverflow.com/questions/51796237/minimum-number-of-swaps-to-convert-a-string-to-palindrome

The question is pretty straightforward in the sense that we just need to make some character swaps to make the given string palindrome, if possible, with the catch that we can swap any two characters which need not be adjacent (unlike the problem: https://www.codechef.com/problems/ENCD12)

I've thought deeply into the possibility of applying concepts from permutation graph and cycle decomposition but it's all been in vain for now :( Yet another possibility is to run a BFS from the starting word exploring all possible swap states but this would be too slow.

I would greatly appreciate if any of you geniuses can provide me with some more hints as to how can I approach this problem in a more efficient manner.

Thank you so much for your time!