我想从 TopCoder 解决这个问题，其中给出了一个字符串，并且在每个步骤中，您必须将所有出现的字符（您选择的）替换为另一个字符（您选择的），以便在最后步骤你得到一个回文。问题是确定替换的最小总数。
到目前为止的想法： 我可以确定每一步之后的字符串只是图中的一个节点/顶点，并且每条边的成本是该步骤中进行的替换次数，但我不知道如何使用贪婪那（这绝对不是最小生成树问题）。我认为识别所有可能的节点和边缘成本并将问题转换为最短路径问题是没有意义的。另一方面，我认为在每一步中，将字符 X 替换为冲突次数最多的字符是有意义的，而字符 Y 与字符串中出现最多的 X 冲突。
无论如何，我也无法证明它有效。我也无法确定任何已知问题。有任何想法吗？
您需要识别分离的字符集。分离的字符集是一组字符，它们都必须变成相同的字符才能使字符串成为回文。
例子：
假设我们有字符串 abcdefgfmdebac
它有 3 个分离集abc，de和fgm
算法：
选择第一个字符并检查它在集合中拾取其他字符的所有出现。在示例字符串中，我们开始a并拾取band （因为它们位于我们字符串c中两者的相对侧）。我们对和a重复这个过程，但没有新字符添加到集合中。我们的第一个析取集也是如此。对剩余的字符继续执行此操作。bcabc
一组分离的n字符（计算所有字符）需要n-m替换，其中 m 是最常见字符的出现次数。所以简单地总结集合。
在我们的示例中，它需要 4 + 2 + 2 = 8 次替换。