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

Given **N** strings, print the maximum length of the string and the string formed by concatenating any of the **N** strings, such that every letter in the string occurs even number of times

**Example: **

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 5, str = [“ABAB”, “ABF”, “CDA”, “AD”, “CCC”]Output: ABABCDAADCCC 12Explanation:The string formed by concatenation is ABABCDAADCCC. Each letter in the string occurs even number of times

Input:N = 3, str = [“AB”, “BC”, “CA”]Output:ABBCCA 6Explanation:The string formed by concatenation of all 3 strings is ABBCCA

**Approach**: The given problem can be solved using recursion and backtracking. The idea is to either include the string or exclude the string at every iteration. After including a string, the frequency of all the characters in the concatenated string is calculated. If frequency of all the characters is even we update the maximum length **max. **Below steps can be followed to solve the problem:

- Initialize variable
**max**to 0 for calculating maximum length of concatenated string having even frequency of all characters - Initialize string
**ans1**to store the concatenated string of maximum length with all character having even frequency - The base case of the recursive call is to return, if
**index**becomes equal to the size of the input string list - At every recursive call we perform the following operation:
- Include the string and check if the frequency of characters is even for the concatenated string
- If the frequency is even, update
**max**and**ans1** - Increment the index and make the next recursive call

- If the frequency is even, update
- Exclude the string, increment the index and make the next recursive call

- Include the string and check if the frequency of characters is even for the concatenated string

Below is the implementation of the above approach:

## C++

`// C++ implementation of the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `int` `maxi = 0;` `string ans1 = ` `""` `;` `// Function to check the string` `void` `calculate(string ans)` `{` ` ` `int` `dp[26] = { 0 };` ` ` `for` `(` `int` `i = 0; i < ans.length(); ++i) {` ` ` `// Count the frequency` ` ` `// of the string` ` ` `dp[ans[i] - ` `'A'` `]++;` ` ` `}` ` ` `// Check the frequency of the string` ` ` `for` `(` `int` `i = 0; i < 26; ++i) {` ` ` `if` `(dp[i] % 2 == 1) {` ` ` `return` `;` ` ` `}` ` ` `}` ` ` `if` `(maxi < ans.length()) {` ` ` `// Store the length` ` ` `// of the new String` ` ` `maxi = ans.length();` ` ` `ans1 = ans;` ` ` `}` `}` `// Function to find the longest` `// concatenated string having` `// every character of even frequency` `void` `longestString(vector<string> arr, ` `int` `index,` ` ` `string str)` `{` ` ` `// Checking the string` ` ` `if` `(index == arr.size()) {` ` ` `return` `;` ` ` `}` ` ` `// Dont Include the string` ` ` `longestString(arr, index + 1, str);` ` ` `// Include the string` ` ` `str += arr[index];` ` ` `calculate(str);` ` ` `longestString(arr, index + 1, str);` `}` `// Driver code` `int` `main()` `{` ` ` `vector<string> A` ` ` `= { ` `"ABAB"` `, ` `"ABF"` `, ` `"CDA"` `, ` `"AD"` `, ` `"CCC"` `};` ` ` ` ` `// Call the function` ` ` `longestString(A, 0, ` `""` `);` ` ` `// Print the answer` ` ` `cout << ans1 << ` `" "` `<< ans1.length();` ` ` `return` `0;` `}` `// This code is contributed by Potta Lokesh` |

## Java

`// Java Implementation of the above approach` `import` `java.io.*;` `import` `java.util.*;` `public` `class` `index {` ` ` `static` `int` `max = ` `0` `;` ` ` `static` `String ans1 = ` `""` `;` ` ` `// Function to check the string` ` ` `static` `void` `calculate(String ans)` ` ` `{` ` ` `int` `dp[] = ` `new` `int` `[` `26` `];` ` ` `for` `(` `int` `i = ` `0` `; i < ans.length(); ++i) {` ` ` `// Count the frequency` ` ` `// of the string` ` ` `dp[ans.charAt(i) - ` `'A'` `]++;` ` ` `}` ` ` `// Check the frequency of the string` ` ` `for` `(` `int` `i = ` `0` `; i < dp.length; ++i) {` ` ` `if` `(dp[i] % ` `2` `== ` `1` `) {` ` ` `return` `;` ` ` `}` ` ` `}` ` ` `if` `(max < ans.length()) {` ` ` `// Store the length` ` ` `// of the new String` ` ` `max = ans.length();` ` ` `ans1 = ans;` ` ` `}` ` ` `}` ` ` `// Function to find the longest` ` ` `// concatenated string having` ` ` `// every character of even frequency` ` ` `static` `void` `longestString(` ` ` `List<String> arr, ` `int` `index, String str)` ` ` `{` ` ` `// Checking the string` ` ` `if` `(index == arr.size()) {` ` ` `return` `;` ` ` `}` ` ` `// Dont Include the string` ` ` `longestString(arr, index + ` `1` `, str);` ` ` `// Include the string` ` ` `str += arr.get(index);` ` ` `calculate(str);` ` ` `longestString(arr, index + ` `1` `, str);` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `ArrayList<String> A = ` `new` `ArrayList<>();` ` ` `A.add(` `"ABAB"` `);` ` ` `A.add(` `"ABF"` `);` ` ` `A.add(` `"CDA"` `);` ` ` `A.add(` `"AD"` `);` ` ` `A.add(` `"CCC"` `);` ` ` `// Call the function` ` ` `longestString(A, ` `0` `, ` `""` `);` ` ` `// Print the answer` ` ` `System.out.println(ans1 + ` `" "` ` ` `+ ans1.length());` ` ` `}` `}` |

**Output**

ABABCDAADCCC 12

**Time Complexity: **O(M*N* (2^N)), where N is the number of strings and M is the length of the longest string**Auxiliary Space: **O(N)

**Another Approach: **The above approach can be further optimized by precomputing the frequency of characters for every string and updating the frequency array after concatenation of each string.