Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-  
2.
Solution Approach 
3.
Algorithm -
4.
C++ code:
4.1.
Output:
5.
Algorithm Complexity: 
6.
Frequently asked questions-
7.
Key takeaways-
Last Updated: Mar 27, 2024

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

Author Riya
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction-  

This blog will discuss the problem of finding the maximum length of a string having even frequency of each character formed by concatenation.

In this problem, we will be given an array containing 'N' strings, and we have to find the maximum length of a string having even frequency of each character formed by concatenation of any of the strings from the given array.

 

Let’s understand the problem with an example:

Suppose N = 5 and

arr[5] = {"abf", "cda", "abab", "ccc",  "ad"}

 

In this example, if we will create a string by concatenation of the last four strings of the array, the following string will be formed:

"cdaababcccad"

We can see in this string that 

Frequency of 'a' = 4

Frequency of 'b' = 2

Frequency of 'c' = 4

Frequency of 'd' = 2


In this concatenated string, the frequency of each character is even. The longest string having even frequency of each character formed by concatenation of strings from the given array of strings is "cdaababcccad." Thus, the maximum length of a string having even frequency of each character formed by concatenation is 12 (length of "cdaababcccad" is 12). 

 

Now that we understand the problem, let's discuss the approach to solve it in the next section.

Also see about, kth largest element in an array

Solution Approach 

This section will discuss the approach to find the maximum length of a string having even frequency of each character formed by concatenation of any of the strings from the given array of strings. The approach is based on recursion and backtracking. For each string in the array, we have two choices - either include it into our resultant string having even frequency of each character or don't include it. So, the idea is to create a recursive function and call it recursively twice for each string - one after including it and another without including it. After including each string, keep checking whether all the characters in the resultant string have even frequency, and keep updating the maximum length of a string having even frequency of each character formed by concatenation.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

Output:

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

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 -

Recommended Readings:

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.

Previous article
Print all the Balanced Brackets Strings that can be formed by replacing '?' in string
Next article
Arrange Elements of Given Array in a Mathematical Expression using Operators [+, -, *, /] and Parentheses to Get Value 28
Live masterclass