In this post I \'m not trying to give the most efficient algorithm or the simplest code. I just try to explain the essence of the problem.\n\nA palindrome is an axial symmetry string. Every position holds the same letter with its position symmetry. \n\n drawing

\n\n\n\nThe most common idea that we can come up with is using two pointers for the left end and right end. If the current two letters are the same, we advance the pointer. If not, we search for the nearest letter that will make them same and swap it. Look at the following example. \n1. The current two letters \'a\' and \'d\' are different. \n2. We need to exchange one of them to be the same with the other. Notice here, you may keep either one of them. Though the final string may be different, the count of moves we spend are equal(you\'ll see that later). Here let\'s keep the right end letter \'d\' and search for the nearest \'d\' from the left end.\n\n drawing

\n\n3. After we find the nearest \'d\', we need to swap it to the 0-position.\n\n drawing

\n\n4. We advance the two pointers and repeat the same steps until the two pointers meet.\n\n drawing

\n\n\nI believe the aforementioned method is easy to understand. However, the difficulty is how we can know the method leads to the minimum moves. Can we convert the string to an arbitrary palindrome with minimal moves? If not, what kind of string we can convert to with minimal moves?\n\n**The key point is relative order between the letters.**\n\nSince the palindrome is axial symmetry, the same letter pair in the left part and right part must have the opposite relative order. So if two letter pairs have the same relative order, you can\'t avoid swapping them. In the meantime, if two letter pairs already have the opposite relative order, you should avoid swapping them, or you\'ll introduce redundant moves and lead to non-optimal solution.\n\nLet\'s look at the example now. All the letters in the left part and right part have the same order. \n\n drawing

\n\nSo you need to swap letters to make all the letter pairs in left and right opposite. You don\'t have to start from the end, and you can convert either left part or right part. Though this can lead to different palindrome, they all cost the same moves. See the below moves which randomly select the letter pair to swap. After 6 moves, it ends with a different palindrome compared to the former solution.\n\n drawing

\n\nWhen we say "randomly" here, it means the order of the letter pair we swap. In fact, you can see that all the letter pairs we swap are exactly the combination of the 4 letters \'abcd\'. That\'s why we need 6 moves. We swap every letter pair because in this example, all the letter pair from left and right have the same order. So they all need to be swapped once each. \nLet\'s look at another example. \n\n drawing

\n\nIn this example, let\'s compare the letter pairs relative order in left and right side.\n(a, b) -- (b, a) -- opposite\n(a, c) -- (c, a) -- opposite\n(a, d) -- (a, d) -- same\n(b, c) -- (b, c) -- same\n(b, d) -- (b, d) -- same\n(c, d) -- (c, d) -- same\nSo, we need to swap 4 letter pairs at least.\n\nWe see that (a, b) and (a, c) pair already have the opposite order in the left and right side. So they don\'t need to be swapped again. But for all the other 4 letter pairs, they still need to be swapped. During your solution you should avoid swapping the letter pair that are already in their right order. \nSee below, you should not try to swap (c,d) first, which will cause (c, a) be swapped. The same with (b, d).\n\n drawing

\n\n\nSo you can swap (a,d) or (b,c) either you like.\n\n\n drawing

\n\nAfter 4 moves, we get to the end.\n\nTill now, let\'s answer the question posed earlier. What kind of palindrome can we convert to with minimal moves? The answer should be the palindromes that keep the letter pair order which have already met the conditions. \nIn the above example "abcdbcad", palindromes like "cabddbac", "bacddcab" are definitely impossible with minimal moves to convert to. Because they require to swap (a,c), (a, b) which are already in good state.\n\nLet\'s try a little more tricky example. The letters are not located on their target side. So what we should keep in mind is just do the necessary swap. \n\n drawing

\n\nFirst, we need to know which letter belongs to which side. We should choose the closest letters to each side in order to reduce the moves. Green ones belong to the left side while blue ones belong to the right side.\n\n drawing

\n\nNow, besides keeping the relative orders, we still need to think about the side. We can not avoid the moves that swap all the blue ones to the right of the green ones.\n\n drawing

\n\n\nFinally, let\'s see why the two pointers algorithm work well. See below, if you keep right end \'d\' still, you know that all the other letters are to its left. So when you find and swap the nearest \'d\' to left end , you are sure that every single swap you make isn\'t unnecessary, because \'d\' should be in front of all of them. \n\n drawing

\n\n\nAfter the whole idea is clear, let\'s talk a little bit about a special case we need to notice. When the string length is odd, there must be a letter that has no partner. See the following example, the \'z\' has no counterpart. So when we try to search \'z\' from the left end, we will end up meeting the right end pointer q. In that case, we know \'z\' should be the centerpoint of the result. \n\n drawing

\n\nYou can record the position of \'z\' and advance the q pointer. At the end of the whole process, you can swap \'z\' to the centerpoint. Notice here, you should avoid trying to swap the \'z\' to the center before the whole process ends. That is because at this time you can\'t guarantee all the swap you do is necessary. See the example below. The green \'d\' is swapped to the right side of \'z\' which is an unnecessary cost, because it should be on the left size at the end. However, when you do this after the whole process ends, you won\'t have this problem.\n drawing

\n\n```\nindrome(string s) {\n \n int l = 0;\n int r = s.length() - 1;\n\n int count = 0;\n int center_i = -1;\n \n while (l < r) {\n if (s[l] == s[r]) {\n l++;\n r--;\n continue;\n }\n\n int k = l + 1;\n for (; k < r; k++) {\n if (s[k] == s[r]) {\n break;\n }\n }\n\n if (k == r) {\n center_i = r;\n r--;\n continue;\n }\n\n for (int j = k; j > l; j--) {\n swapChar(j, j - 1);\n count++;\n }\n \n l++;\n r--;\n }\n \n if (center_i != -1) {\n count += (center_i - s.size() / 2);\n } \n \n return count;\n }\n};\n```

Minimum Number of Moves to Make Palindrome

Problem Description

Problem Description

Answer Panel