Minimum number of char substitutions to get a palindrome

Question

I would like to solve this problem from TopCoder, in which a String is given and in each step you have to replace all occurrences of an character (of your choice) with another character (of your choice), so that at the end after all steps you get a palindrome. The problem is to identify the minimum total number of replacements.

Ideas so far: I can identify that the string after every step is simply a node/vertex in a graph and that the cost of every edge is the number of replacements made in the step, but I don't see how to use greedy for that (it is definitely not the Minimum Spanning Tree problem). I don't think it makes sense to identify all possible nodes & edge costs and to convert the problem in the Shortest Path problem. On the other side, I think in every step it makes sense to replace the character X with the biggest number of conflicts, with the character Y in conflict with X that occurs most in the string.

Anyway, I can't either prove that it works. Also I can't identify any known problems in this. Any ideas?

Answer 1

You need to identify disjunct sets of characters. A disjunct set of characters is a set of characters that will all have to become the same character in order for the string to become a palindrome.

Example:

Let's say we have the string abcdefgfmdebac

It has 3 disjunct sets, abc, de and fgm

Algorithm:

1. Pick the first character and check all occurences of it picking up other characters in the set. In the example string we start with a and pick up band c (because they sit on the opposite sides of the two ain our string). We repeat the process for band c, but no new characters are added to the set. So abc is our first disjunct set. Continue doing this with the remaining characters.

2. A disjunct set of n characters (counting all characters) needs n-m replacements, where m is the number of occurences of the most frequent character. So simply sum over the sets.

In our example it takes 4 + 2 + 2 = 8 replacements.