Maximum length of a string having even frequency of each character formed by concatenation

Algorithm -

Step 1. Create a function "maxLengthString()" to find the maximum length of a string having even frequency of each character formed by concatenation. It takes the following inputs:

1. arr - An array of strings
2. index - Current index of the array 
3. N - Size of the given array
4. str - string formed by the concatenation till now
5. maxLen - variable to store the maximum length of a string having even frequency of each character formed by concatenation

Step 2. Inside the function "maxLengthString()," first write the base case that if the index is equal to N, then return. Then first, don't include the string at the current index in the array and call the function recursively for the next index. After this, include the string at the current index into the resultant string and check the frequency of each character. If the frequency of each character is even, then update the value of 'maxLen .'Finally, call the function recursively for the next index.

Step 3. Write a function "isValid()" which takes a string as input and returns true if the frequency of each character in the string is even, else return false. Inside the function, create a frequency array to store the frequency of each character and then check whether the frequency of each character is even or odd.

Step 4. Finally, write the main function. Initialize the variable 'maxLen" as 0 and call the function "maxLengthString()" by passing the required parameters. Please note that the variable 'maxLen' is passed b address so that the function can change its value.

C++ code:

// C++ code to find the maximum length of a string having even frequency of each character formed by concatenation #include <bits/stdc++.h> using namespace std; // Function to check whether the string has even frequency of each character bool isValid(string str) { int freq[26] = { 0 }; // Store the frequency of each character for (int i = 0; i < str.length(); i++) { freq[str[i] - 'a']++; } // Check if the frequency of any character is odd, return false for (int i = 0; i < 26; i++) { if (freq[i] % 2 == 1) { return false; } } return true; } // Function to find the maximum length of a string having even frequency of each character formed by concatenation void maxLengthString(string arr[], int index, int N, string str, int& maxLen) { // Checking the string if (index == N) { return; } // Dont Include the string maxLengthString(arr, index + 1, N, str, maxLen); // Include the string str += arr[index]; if(isValid(str)) { if(str.length() > maxLen) { maxLen = str.length(); } } maxLengthString(arr, index + 1, N, str, maxLen); } // Main function int main() { int N = 5;    string arr[5] = {"abf", "cda", "abab", "ccc",  "ad"};       // Varriable to store the maximum length of string having even frequency of each character formed by concatenation    int maxLen = 0;    // Call the function to find the maximum length of a string having even frequency of each character formed by concatenation maxLengthString(arr, 0, N, "", maxLen); // Print the answer cout <<"The maximum length of a string having even frequency of each character formed by concatenation is: "<<maxLen<<endl; return 0; } You can also try this code with Online C++ Compiler Run Code

Output:

The maximum length of a string having even frequency of each character formed by concatenation is: 12

You can also try this code with Online C++ Compiler

Run Code

Also check out - Substr C++

Algorithm Complexity: 

Time Complexity: O(N * M* log(N))

In the function "maxLengthString()" to find the maximum length of a string having even frequency of each character formed by concatenation, two recursive calls are made for each string of the array, which will take 2 ^ N time. For each string, the concatenation and checking the frequency of each character will take O(length of the concatenated string) time. In the worst case, the length of the concatenated string will be O(N * M)  So, the overall time complexity is O(N * M * log(2 ^ N)), where 'N' is the number of strings in the given array and 'M' is the length of the longest string in the array.

Space Complexity: O(1) 

We have used constant space in the function "maxLengthString()" to find the maximum length of a string having an even frequency of each character formed by concatenation. So, the space complexity is O(1).

Frequently asked questions-

1. What is meant by the concatenation of two strings?
   Concatenation of two strings means the addition of two strings.
    
2. In the above solution, why we have made the “freq” array of size 26 inside the ‘isValid()’ function?
   We have assumed that the given strings will contain only small alphabets. So, we have made the ‘freq’ array of size 26 to store the frequency of each character of the 26 small alphabets.

Key takeaways-

This article discussed the problem  “Maximum length of string having even frequency of each character formed by concatenation”, the solution approach to this problem,  its C++ implementation, and its time and space complexity.

If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

 Check out this article - C++ String Concatenation

Recommended problems -

• Find the Shortest Substring in a String
• Subsequence of a String
• Beautiful String
   

Recommended Readings:

• Python String Concatenation
   

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.