C++ 每个字符的频率是偶数形成的字符串的最大长度

拼接是一个运算符，用于连接一个或多个字符串以生成一个新的字符串，该字符串是由生成它的字符串的组合形成的。在以下文章中，我们只在输入字符串中使用大写字母。

现在，在这个问题中，我们需要找到由每个字符的频率为偶数形成的字符串的最大长度，其中该字符串将是用户提供给我们的输入。让我们看看我们应该如何解决这个问题。

让我们通过一些示例来理解这个问题。

输入 – “FEFEE”，”EFF”，”HGG”，”AD”，”HHH”

输出 – 14

解释 – 在这个示例中，我们可以看到通过拼接由每个字符频率为偶数形成的字符串的最大长度是“FEFEEEFFHGGHHH”，并且我们得到的字符串的长度为14。因此，“14”是最终输出。

F的频率− 4
E的频率− 4
H的频率− 4
G的频率− 2

输入 – “ABCD”，”AVP”，”ADDDC”，”BCCCA”，”HH”，”CA”

输出 – 18

解释 – 在这个示例中，我们可以看到通过拼接由每个字符频率为偶数形成的字符串的最大长度是“ABCDADDDCBCCCAHHCA”，并且我们得到的字符串的长度为18。因此，“18”是最终输出。

A的频率：4
B的频率：2
C的频率：6
D的频率：4
H的频率：2

问题解释

让我们尝试理解问题并找到解决方案。在以下文章中，我们将讨论从给定的字符串数组中查找由串联形成的具有每个字符的偶数频率的字符串的最大长度的方法。解决方案将涉及递归和回溯。对于数组中的每个字符串，我们有两个选择：要么将其包含在具有每个字符的偶数频率的最终字符串中，要么不包含该字符串。因此，该方法涉及创建一个递归函数，并为每个字符串递归调用它两次 – 一次包括它，一次不包括它。在包括每个字符串之后，不断检查最终字符串中的所有字符是否具有偶数频率，并不断更新由拼接形成的具有每个字符的偶数频率的字符串的最大长度。

递归算法

创建一个递归函数，以当索引等于数组大小时的基本情况为准，函数将返回。现在，在该函数中，我们将有两种情况，第一种情况是不包括当前字符串，进行递归调用。
而在第二种情况中，我们将包括它，然后通过使用另一个函数（CheckValid）来检查当前输出字符串是否满足要求，即每个字符都具有偶数频率。
如果满足要求，我们将保存该字符串的长度，如果大于先前的大小。
接下来，我们将进行另一个递归调用，其中将包括当前字符串。
这样，我们将达到最终的输出大小。

示例C++代码实现

#include <bits/stdc++.h>
using namespace std;
// Function to check whether the string has an even frequency of each character or not
bool CheckValid(string str){
   // Declare a frequency array that would work like a map to store the count of each alphabet
   int mapArray[26] = { 0 };
   // Store the frequency of each alphabet, we will take uppercase English alphabets only in our string
   for (int i = 0; i < str.length(); i++){
      mapArray[str[i] - 'A']++;
   }
   // Check if the frequency of any alphabet is odd, if yes return false
   for (int i = 0; i < 26; i++){
      if (mapArray[i] % 2 == 1){
          return false;
      }
   }
   // If we have all our alphabets in even count, we can return true
   return true;
}
// Function to find the maximum length of a string having an even frequency of each character formed by concatenation
void FindMaxLength(string array[], int i, int size, string s, int& maxi){
   // Check if we have taken all strings from our array that is check the base case
   if (i == size) {
      return;
   }    
   // Do not Include the string
   FindMaxLength(array, i + 1, size, s, maxi);
   // Include the string
   s += array[i];
   // Check if the string collected is giving us a string with all character counts as even, constituted in it
   if(CheckValid(s)) {
      // Store the maximum of the previous and current length
      if(s.length() > maxi) {
          maxi = s.length();
      }
   }
   FindMaxLength(array, i + 1, size, s, maxi);
}
int main(){
   // Size of the string provided by the user
   int size = 5;
   // String provided by the user
   string array[5] = { "FEFEE", "EFF", "HGG", "AD", "HHH" };    
   // Declare a variable to store the maximum length of string formed by concatenation having even frequency of each character
   int maxi = 0;    
   // Call the function to find the maximum length of string formed by concatenation having an even frequency of each character
   FindMaxLength(array, 0, size, "", maxi);
   // Print the final output
   cout << "The maximum length of string formed by concatenation having an even frequency of each character is: "<< maxi <<endl;
   return 0;
}

输出

The maximum length of string formed by concatenation having an even frequency of each character is: 14

上述代码的复杂性

时间复杂度：O(n * m * (2^n)))；其中’n’是给定字符串数组的长度，即字符串的总数，’m’是数组中最长字符串的长度。每个字符串在递归调用中将被执行两次，使得该递归函数的时间复杂度为’2^n’，而CheckValid函数的时间复杂度将花费最长长度的字符串形成的连接串的总时间，它可能最高达到(n * m)，这是当我们将给定数组中的每个字符串都包含在我们的最终答案中时的情况。
空间复杂度：O(1)；我们在上述代码中没有存储任何变量在某个数据结构中。