需要移除的最小字符数，以便字符串可以重新排列形成回文

---

在这个问题中，我们需要从字符串中移除最少的字符，并将剩余的字符重新排列以使字符串成为回文。

为了解决这个问题，我们首先应该问自己的问题是何时可以使字符串成为回文。在以下两种情况下，我们可以使字符串成为回文。

• 如果给定字符串中每个字符的频率都是偶数。

• 如果只有一个字符的频率是奇数，而所有其他字符的频率都是偶数。

因此，我们需要移除最少的字符以使每个字符的频率为偶数，除了任何单个字符。

问题陈述 - 我们给定一个包含 N 个小写字母字符的字符串 str。我们需要从给定的字符串中移除最少的字符，以便我们可以通过重新排列剩余的字符来创建一个回文字符串。

示例

Input –  str = "abcabccd"

Output – 1

解释

这里，我们需要移除 'c' 或 'd' 字符。

Input –  str = ‘aabbc’

Output – 0

解释

我们不需要移除任何字符，因为我们可以从给定的字符串中创建一个 'abcba' 回文字符串。

Input –  str = ‘pqrstvu’

Output – 6

解释

为了使给定的字符串成为回文，我们必须移除所有字符，除了一个。我们只能使用此字符串创建一个长度为 1 的回文字符串。

方法 1

在这种方法中，我们将计算给定字符串中每个字符的频率。之后，我们将计算频率为奇数的字符总数。我们需要只保留一个频率为奇数的字符，并移除其他字符以使其频率为偶数。

算法

• 步骤 1 - 定义长度等于 26 的 'freq' 数组。

• 步骤 2 - 使用 memset() 方法将所有数组元素初始化为 0。

• 步骤 3 - 遍历字符串并在 'freq' 数组中存储每个字符的频率。

• 步骤 4 - 将 'cnt' 变量初始化为 0。

• 步骤 5 - 现在，遍历 'freq' 数组，如果数组中当前索引处的值为奇数，则将 'cnt' 的值增加 1。

• 步骤 6 - 如果 'cnt' 变量的最终值为 0 或 1，则返回 0。

• 步骤 7 - 返回 'cnt – 1'，因为我们可以保留一个频率为奇数的字符。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the minimum number of deletions required to make string palindrome
int deletionCount(string str){    
   int fre[26]; // array of size 26, which stores the frequency of each character
   memset(fre, 0, sizeof(fre));     // Initialize array with 0
   int n = str.size();
   
   // cnt frequency of each character in the string
   for (int i = 0; i < n; i++){
      fre[str[i] - 'a'] += 1;
   }
   int cnt = 0;
   
   // find the number of characters with odd frequency
   for (int i = 0; i < 26; i++){
      if (fre[i] % 2){
         cnt += 1;
      }
   }
   
   // If characters with odd frequency are 0 or 1, then the string can be palindrome without any character deletion
   if (cnt == 0 || cnt == 1){
      return 0;
   }
   
   // Otherwise, return cnt - 1, as one character can be odd
   else{
      return cnt - 1;
   }
}
int main(){
   string str = "abcabccd";
   cout << "The minimum number of deletions of characters required to make string palindrome is - " << deletionCount(str) << endl;
}

输出

The minimum number of deletions of characters required to make string palindrome is - 1

时间复杂度 - O(N)，因为我们计算给定字符串中每个字符的频率。

空间复杂度 - O(1)，因为我们使用常数空间。

结论

我们学习了如何找到排列剩余字符以形成回文字符串所需的最小字符移除数。我们使用 'freq' 数组来存储每个字符的频率，但用户也可以使用 count() 方法来计算给定字符串中特定字符的频率。