0
$\begingroup$

Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols (UVA 10716). I've found an AC solution with the following greedy algorithm (from UVA board): "For each letter find it's first and last occurence in current string. Select letter for which sum of distances from its first occurence to beginning and from last one to the end is smallest. Swap its first occurence to beginning and last to the end. And "eliminate" them --> now you have the word which is shorter. You have to repeat until you have <=1 letters left."

But I can't find the proof (and I can't construct it by myself). The question: how to prove the correctness of the algorithm?

$\endgroup$
  • $\begingroup$ Start with the following questions - Is your algorithm recursive or iterative ? Since, it's iterative ... Try to look for an invariant. $\endgroup$ – user230452 Jun 26 '16 at 14:34
  • $\begingroup$ Can every string be converted to a palindrome ? Consider the word 'palindrome' itself. Each letter only occurs once so it can't be transformed into a palindrome. Is there some constraint that needs to be applied ? Like each letter should occur an even number of times with at most one letter occurring an odd number of times ? $\endgroup$ – user230452 Jun 26 '16 at 14:38
  • 3
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 26 '16 at 15:31
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 26 '16 at 15:31
  • $\begingroup$ @user230452, yes, of course, there are some constraints (the string can be converted to a palindrome if and only if the count of characters with odd number of occurences is <= 1). My question is about the algorithm I've written about (we can consider only the strings that can be transformed to the palindrome). $\endgroup$ – Alexander_KH Jun 27 '16 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.