Longitud máxima de string formada por concatenación que tiene una frecuencia uniforme de cada carácter

Dadas N strings , imprima la longitud máxima de la string y la string formada al concatenar cualquiera de las N strings, de modo que cada letra de la string ocurra un número par de veces 

Ejemplo: 

Entrada: N = 5, str = [“ABAB”, “ABF”, “CDA”, “AD”, “CCC”]
Salida : ABABCDAADCCC 12
Explicación: La string formada por concatenación es ABABCDAADCCC. Cada letra de la string aparece un número par de veces

Entrada: N = 3, str = [“AB”, “BC”, “CA”]
Salida: ABBCCA 6
Explicación: La string formada por la concatenación de las 3 strings es ABBCCA

Enfoque : El problema dado se puede resolver usando recursividad y retroceso . La idea es incluir la string o excluir la string en cada iteración. Después de incluir una string, se calcula la frecuencia de todos los caracteres de la string concatenada. Si la frecuencia de todos los caracteres es par, actualizamos la longitud máxima max. Se pueden seguir los siguientes pasos para resolver el problema:

• Inicialice la variable max a 0 para calcular la longitud máxima de la string concatenada que tiene una frecuencia uniforme de todos los caracteres
• Inicialice la string ans1 para almacenar la string concatenada de longitud máxima con todos los caracteres que tienen una frecuencia uniforme
• El caso base de la llamada recursiva es regresar, si el índice se vuelve igual al tamaño de la lista de strings de entrada
• En cada llamada recursiva realizamos la siguiente operación:
  • Incluya la string y verifique si la frecuencia de caracteres es uniforme para la string concatenada
    • Si la frecuencia es uniforme, actualice max y ans1
    • Incrementa el índice y realiza la siguiente llamada recursiva.
  • Excluya la string, incremente el índice y realice la siguiente llamada recursiva

A continuación se muestra la implementación del enfoque anterior:

// 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 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());
    }
}

# Python3 implementation of the above approach
maxi = 0;
ans1 = "";
 
# Function to check the string
def calculate(ans) :
     
    global maxi,ans1;
     
    dp = [ 0 ] * 26;
    for i in range(len(ans)) :
 
        # Count the frequency
        # of the string
        dp[ord(ans[i]) - ord('A')] += 1;
 
    # Check the frequency of the string
    for i in range(26) :
        if (dp[i] % 2 == 1) :
            return;
         
    if (maxi < len(ans)) :
 
        # Store the length
        # of the new String
        maxi = len(ans);
        ans1 = ans;
 
# Function to find the longest
# concatenated string having
# every character of even frequency
def longestString( arr,  index, string) :
 
 
    # Checking the string
    if (index == len(arr)) :
        return;
 
    # Dont Include the string
    longestString(arr, index + 1, string);
 
    # Include the string
    string += arr[index];
 
    calculate(string);
    longestString(arr, index + 1, string);
 
 
# Driver code
if __name__ == "__main__" :
 
    A = [ "ABAB", "ABF", "CDA", "AD", "CCC" ];
   
    # Call the function
    longestString(A, 0, "");
 
    # Print the answer
    print(ans1, len(ans1));
 
    # This code is contributed by AnkThon

// C# Implementation of the above approach
using System;
 
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[(int)ans[i] - (int)'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(String[] arr, int index, String str)
    {
 
        // Checking the string
        if (index == arr.Length) {
            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
    public static void Main()
    {
        String[] A = {"ABAB", "ABF", "CDA", "AD", "CCC"};
 
        // Call the function
        longestString(A, 0, "");
 
        // Print the answer
        Console.WriteLine(ans1 + " " + ans1.Length);
    }
}
 
// This code is contributed by saurabh_jaiswal.

<script>
// Javascript implementation of the above approach
 
let maxi = 0;
let ans1 = "";
 
// Function to check the string
function calculate(ans) {
  let dp = new Array(26).fill(0);
  for (let i = 0; i < ans.length; ++i) {
    // Count the frequency
    // of the string
    dp[ans[i].charCodeAt(0) - "A".charCodeAt(0)]++;
  }
 
  // Check the frequency of the string
  for (let 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
function longestString(arr, index, str) {
  // Checking the string
  if (index == arr.length) {
    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
 
let A = ["ABAB", "ABF", "CDA", "AD", "CCC"];
 
// Call the function
longestString(A, 0, "");
 
// Print the answer
document.write(ans1 + " " + ans1.length);
 
// This code is contributed by gfgking
 
</script>

ABABCDAADCCC 12

Complejidad de tiempo: O(M*N* (2^N)), donde N es el número de strings y M es la longitud de la string más larga
Espacio auxiliar: O(N)

Otro enfoque: el enfoque anterior se puede optimizar aún más calculando previamente la frecuencia de los caracteres para cada string y actualizando la array de frecuencias después de la concatenación de cada string.