fakeacc007's blog

Need assistance in solving: Minimum number of swaps to make a string palindrome
By fakeacc007, history, 5 years ago, In English

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!

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider the ends of the current string let's say current string is a???b in the optimal solution either both of these ends are a or both of these ends are b, and we have to place the character at the ends which has least cost at that instant so it's a greedy algorithm choose the character to be placed at the end which has least cost and then our string length decreases by 2 , I don't have a proof for this though.

→ Reply
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I am stuck on the same problem. Is your cycle decomposition too slow ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the accepted answer of the stackoverflow question provides some good intuition.

Let's consider even $$$n$$$. For all pairs of positions $$$(i, n-i-1)$$$ for which $$$s_i \neq s_{n-i-1}$$$ add an undirected edge in $$$G$$$ from $$$s_i$$$ to $$$s_{n-i-1}$$$. This ultimately forms a multigraph $$$G$$$ of $$$\Sigma$$$ nodes. Now, it seems that solving the problem corresponds to decomposing this multigraph into as many edge-disjoint cycles as possible.

It seems that the discussion here suggests that this problem is NP-complete (although I can't verify the source). However, this only says that one can't expect a solution polynomial in $$$\Sigma$$$; maybe there are solutions polynomial in the string's length but exponential in $$$\Sigma$$$.

Please correct me if I'm wrong.

→ Reply