C++ 最少删除次数，使字符串可以重新排列成回文形式

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

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

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

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

因此，我们需要删除最少的字符，使得每个字符的频率都是偶数，除了一个单独的字符。

问题陈述 −我们给出一个包含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()方法统计给定字符串中特定字符的频率。