在允许排列的情况下形成回文所需的最少插入次数

回文串是指正读和反读都相同的单词。要写成回文串，我们应该确保字符串中的每个字符都有一个对称的伙伴（只有相同或反向的字符）。

方法 - 1

方法如下：

1. 计算给定字符串中每个字符的出现频率。
2. 一个字符串要成为回文串，每个字符都应该有偶数次出现，最多只能有一个字符出现奇数次。因此，出现奇数次的字符数量超过一个就无法生成回文串。
3. 遍历字符频率
   • 对于偶数次的出现，我们不需要任何插入，因为它们在回文串的另一侧可以配对。
   • 对于奇数次的出现，对于每个字符，需要插入（计数-1）个字符来找到它的匹配项。如果计数是奇数，这意味着单个字符将在中间孤立，从而形成一个回文串。
   • 如果存在多个未配对的字符（即，有多个字符出现奇数次），那么这些字符就不能作为回文串的开头和结尾。否则，返回所需的总插入次数。

让我们通过一个例子来说明这一点

给定字符串“aabbcc”，字符频率计数为

'a': 2

'b': 2

'c': 2

由于每个字符都应该有偶数次出现，因此不需要插入。反转后的单词是“abccba”。

Java 代码实现

输出

说明

1. 频率计数：第一步是确定每个字符的频率以及字符串的长度。我们使用 Hashmap 将字符映射到其频率值。
2. 确定奇数次出现：计数完频率后，我们遍历每对字符以检查其中奇数次出现的字符。为了构成回文串，我们只允许有一个字符出现奇数次，无论其出现次数是多少，所以我们只统计出现奇数频率的字符数量。
3. 计算总插入次数：因此，第二步是确定可以使原始字符串成为回文串所需的插入次数。为更清楚起见，考虑奇数次出现字符的情况。因此，每个出现奇数次的字符都需要与相邻的先前出现的字符配对。最后，我们计算数组中每个奇数次出现字符需要执行的总插入次数，最终得到答案。
4. 检查回文串的有效性：如果我们发现超过一个字符出现奇数次，这意味着给定的字符串可能无法形成回文串。此外，将所有字符配对以满足对称回文串的要求将是不可能的。在这种情况下，我们将返回-1以表示无法形成回文串。如果只有一个字符出现奇数次，我们需要计算插入的总次数。
5. 主方法：在主函数中，我们提供“abcv”作为示例输入字符串，以揭示解决方案的工作原理。因此，应用了 minInsertions(input) 函数，并打印其输出。

此方法在时间和空间效率方面都是最佳选择，并且可以计算出允许置换形成回文串所需的最少插入次数。

方法二

解决此问题的另一种方法是使用双指针技术。工作原理如下：

• 计算给定字符串中每个字符的出现频率。
• 初始化两个指针，一个从字符串开头开始，另一个从字符串结尾开始。
• 使用这些指针遍历字符串
• 如果两个指针处的字符匹配，则将两个指针都移向中心。
• 如果不匹配，则意味着我们需要在其中一个位置插入字符以使其成为回文串。我们需要决定是在第一个指针的当前位置插入字符，还是在第二个指针的位置插入字符。我们选择能够导致最少插入次数的位置。
• 重复步骤 3，直到指针相遇或交叉。
• 返回所需的总插入次数。

这种方法之所以有效，是因为在每一步，我们都基于在当前指针位置插入字符是否会导致总体最少插入次数来做出决策。

算法

1. 初始化变量

• 引入两个指针：left 和 right。分别指示字符串的开头和结尾。
• 引入变量 insertions 来监视所需的总插入次数。

2. 遍历字符串

使用 while 循环遍历字符串，直到 left 指针不等于 right 指针。

3. 检查指针处的字符

定位由左右指针指示位置的字符。

4. 比较字符

• 如果左右指针处的字符匹配，则表示它们已经对齐，不需要插入。Left++ 和 Right-- 将两个指针移向字符串中心。
• 如果不匹配：检查 left + 1 位置的字符是否与 right 位置的字符匹配。如果为真，则将 left 指针向前移动（left++），因为在 left 指针位置插入会产生更少的插入。
• 如果不是，则检查 right-1 位置的字符是否与 left-1 位置的字符匹配。如果是，则将 right 指针向后移动（right--），因为在 right 指针位置插入会产生更少的插入。
• 如果以上任一条件都不满足，则意味着我们需要在 left 或 right 位置插入一个字符，以使 left 和 right 指针之间的子字符串成为回文串。因此，将两个指针移向中心（left++ 和 right--），并增加 insertions 计数。

5. 继续直到指针相遇

重复步骤 3 和 4，直到 left 指针不等于 right 指针。

6. 返回插入次数

当循环退出时，返回形成回文串所需的总插入次数。

Java 代码实现

输出

说明

1. 初始化指针：引入两个指针，left 和 right，分别指示字符串的开头和结尾。引入变量 insertions 来监视所需的总插入次数。
2. 遍历字符串：我们使用这些指针遍历字符串，直到它们相遇或交叉。
3. 检查指针处的字符
   • 如果左右指针处的字符匹配，则表示它们已经对齐，不需要插入。Left++ 和 Right-- 将两个指针移向字符串中心。
   • 如果不匹配：检查 left + 1 位置的字符是否与 right 位置的字符匹配。如果为真，则将 left 指针向前移动（left++），因为在 left 指针位置插入会产生更少的插入。
   • 如果不是，则检查 right-1 位置的字符是否与 left-1 位置的字符匹配。如果是，则将 right 指针向后移动（right--），因为在 right 指针位置插入会产生更少的插入。
   • 如果以上任一条件都不满足，则意味着我们需要在 left 或 right 位置插入一个字符，以使 left 和 right 指针之间的子字符串成为回文串。因此，将两个指针移向中心（left++ 和 right--），并增加 insertions 计数。
4. 决定插入位置
   • 我们检查在 left 指针位置或 right 指针位置插入字符是否会导致总体最少插入次数。
   • 如果 left + 1 位置的字符与 right 位置的字符匹配，我们向前移动 left 指针（left++），因为在 left 指针位置插入会产生更少的插入。
   • 如果 right - 1 位置的字符与 left 位置的字符匹配，我们向后移动 right 指针（right--），因为在 right 指针位置插入会产生更少的插入。
   • 如果以上任一条件都不成立，我们则将两个指针都移向中心（left++ 和 right--），并将插入计数加一。
5. 重复直到指针相遇：我们重复步骤 3 和 4，直到 left 指针小于 right 指针。
6. 返回插入次数：最后，我们返回形成回文串所需的总插入次数。

这种方法通过在每一步基于哪种插入会最小化总插入次数来做出决策，从而有效地找到形成允许置换的回文串所需的最小插入次数。

上述方法之间的差异

复杂度：方法 1 的时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 是字符串长度。方法 2 的时间复杂度也为 O(N)，但所需空间更少，因为它不存储任何辅助数据结构。

实现：方法 1 遵循简单的迭代和计数过程。因此，大多数学习者都熟悉且易于理解。方法 2 涉及双指针技术和决策逻辑，这增加了算法的复杂性。

结论

总而言之，这两种方法都试图回答同一个问题：需要进行多少次添加才能将字母按不同顺序排列的单词变成回文串。第一种方法使用频率计数和简单的循环，因此，结论给定字符串是否是回文串很容易。第二种方法涉及双指针设计和决策逻辑，虽然可以节省空间，但仍然通过各种插入可能性提供输出。方法 1 更简单，而方法 2 在空间效率方面更高。