Maximice la longitud de la string concatenando caracteres de una array de strings

Encuentre la string más grande posible de caracteres distintos formados usando una combinación de strings dadas. Cualquier string dada debe elegirse por completo o no elegirse en absoluto. 

Ejemplos:

Entrada: strings =”abcd”, “efgh”, “efgh” 
Salida: 8
Explicación: 
Todas las combinaciones posibles son {“”, “abcd”, “efgh”, “abcdefgh”}. 
Por lo tanto, la longitud máxima posible es 8.

Entrada: strings = “123467890” 
Salida: 10
Explicación: 
Todas las combinaciones posibles son: “”, “1234567890”. 
Por lo tanto, la longitud máxima posible es 10. 

Enfoque: La idea es usar Recursión . 

Siga los pasos a continuación para resolver el problema:

• Itere de izquierda a derecha y considere cada string como una posible substring inicial.
• Inicialice un HashSet para almacenar los distintos caracteres encontrados hasta el momento.
• Una vez que se selecciona una string como substring inicial, verifique cada string restante, si solo contiene caracteres que no han aparecido antes. Agregue esta string como una substring a la string actual que se está generando.
• Después de realizar los pasos anteriores, imprima la longitud máxima de una string que se ha generado.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if all the
// string characters are unique
bool check(string s)
{
 
    set<char> a;
 
    // Check for repetition in
    // characters
    for (auto i : s) {
        if (a.count(i))
            return false;
        a.insert(i);
    }
 
    return true;
}
 
// Function to generate all possible strings
// from the given array
vector<string> helper(vector<string>& arr,
                    int ind)
{
 
    // Base case
    if (ind == arr.size())
        return { "" };
 
    // Consider every string as
    // a starting substring and
    // store the generated string
    vector<string> tmp
        = helper(arr, ind + 1);
 
    vector<string> ret(tmp.begin(),
                    tmp.end());
 
    // Add current string to result of
    // other strings and check if
    // characters are unique or not
    for (auto i : tmp) {
        string test = i + arr[ind];
        if (check(test))
            ret.push_back(test);
    }
 
    return ret;
}
 
// Function to find the maximum
// possible length of a string
int maxLength(vector<string>& arr)
{
    vector<string> tmp = helper(arr, 0);
 
    int len = 0;
 
    // Return max length possible
    for (auto i : tmp) {
        len = len > i.size()
                ? len
                : i.size();
    }
 
    // Return the answer
    return len;
}
 
// Driver Code
int main()
{
    vector<string> s;
    s.push_back("abcdefgh");
 
    cout << maxLength(s);
 
    return 0;
}

// Java program to implement 
// the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
 
// Function to check if all the
// string characters are unique
static boolean check(String s)
{
    HashSet<Character> a = new HashSet<>();
     
    // Check for repetition in
    // characters
    for(int i = 0; i < s.length(); i++)
    {
        if (a.contains(s.charAt(i)))
        {
            return false;
        }
        a.add(s.charAt(i));
    }
    return true;
}
 
// Function to generate all possible
//  strings from the given array
static ArrayList<String> helper(ArrayList<String> arr,
                                int ind)
{
    ArrayList<String> fin = new ArrayList<>();
    fin.add("");
       
    // Base case
    if (ind == arr.size() )
        return fin;
     
    // Consider every string as
    // a starting substring and
    // store the generated string
    ArrayList<String> tmp = helper(arr, ind + 1);
     
    ArrayList<String> ret = new ArrayList<>(tmp);
     
    // Add current string to result of
    // other strings and check if
    // characters are unique or not
    for(int i = 0; i < tmp.size(); i++)
    {
        String test = tmp.get(i) +
                      arr.get(ind);
                         
        if (check(test))
            ret.add(test);
    }
    return ret;
}
 
// Function to find the maximum
// possible length of a string
static int maxLength(ArrayList<String> arr)
{
    ArrayList<String> tmp = helper(arr, 0);
     
    int len = 0;
     
    // Return max length possible
    for(int i = 0; i < tmp.size(); i++)
    {
        len = len > tmp.get(i).length() ? len : 
                    tmp.get(i).length();
    }
       
    // Return the answer
    return len;
}
 
// Driver code
public static void main (String[] args)
{
    ArrayList<String> s = new ArrayList<>();
    s.add("abcdefgh");
     
    System.out.println(maxLength(s));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement
# the above approach
  
# Function to check if all the
# string characters are unique
def check(s):
     
    a = set()
  
    # Check for repetition in
    # characters
    for i in s:
        if i in a:
            return False
             
        a.add(i)
  
    return True
  
# Function to generate all possible
# strings from the given array
def helper(arr, ind):
  
    # Base case
    if (ind == len(arr)):
        return [""]
  
    # Consider every string as
    # a starting substring and
    # store the generated string
    tmp = helper(arr, ind + 1)
  
    ret = tmp
  
    # Add current string to result of
    # other strings and check if
    # characters are unique or not
    for i in tmp:
        test = i + arr[ind]
         
        if (check(test)):
            ret.append(test)
  
    return ret
     
# Function to find the maximum
# possible length of a string
def maxLength(arr):
 
    tmp = helper(arr, 0)
  
    l = 0
  
    # Return max length possible
    for i in tmp:
        l = l if l > len(i) else len(i)
  
    # Return the answer
    return l
 
# Driver Code
if __name__=='__main__':
     
    s = []
    s.append("abcdefgh")
  
    print(maxLength(s))
  
# This code is contributed by pratham76

// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
 
class GFG{
     
// Function to check if all the
// string characters are unique
static bool check(string s)
{
 
    HashSet<char> a = new HashSet<char>();
 
    // Check for repetition in
    // characters
    for(int i = 0; i < s.Length; i++)
    {
        if (a.Contains(s[i]))
        {
            return false;
        }
        a.Add(s[i]);
    }
    return true;
}
 
// Function to generate all possible
// strings from the given array
static ArrayList helper(ArrayList arr,
                        int ind)
{
     
    // Base case
    if (ind == arr.Count)
        return new ArrayList(){""};
 
    // Consider every string as
    // a starting substring and
    // store the generated string
    ArrayList tmp = helper(arr, ind + 1);
 
    ArrayList ret = new ArrayList(tmp);
 
    // Add current string to result of
    // other strings and check if
    // characters are unique or not
    for(int i = 0; i < tmp.Count; i++)
    {
        string test = (string)tmp[i] +
                    (string)arr[ind];
                         
        if (check(test))
            ret.Add(test);
    }
    return ret;
}
 
// Function to find the maximum
// possible length of a string
static int maxLength(ArrayList arr)
{
    ArrayList tmp = helper(arr, 0);
 
    int len = 0;
 
    // Return max length possible
    for(int i = 0; i < tmp.Count; i++)
    {
        len = len > ((string)tmp[i]).Length ? len :
                    ((string)tmp[i]).Length;
    }
     
    // Return the answer
    return len;
}
     
// Driver Code
public static void Main(string[] args)
{
    ArrayList s = new ArrayList();
    s.Add("abcdefgh");
 
    Console.Write(maxLength(s));
}
}
 
// This code is contributed by rutvik_56

<script>
    // Javascript program to implement the above approach
     
    // Function to check if all the
    // string characters are unique
    function check(s)
    {
        let a = new Set();
 
        // Check for repetition in
        // characters
        for(let i = 0; i < s.length; i++)
        {
            if (a.has(s[i]))
            {
                return false;
            }
            a.add(s[i]);
        }
        return true;
    }
 
    // Function to generate all possible
    //  strings from the given array
    function helper(arr, ind)
    {
        let fin = [];
        fin.push("");
 
        // Base case
        if (ind == arr.length)
            return fin;
 
        // Consider every string as
        // a starting substring and
        // store the generated string
        let tmp = helper(arr, ind + 1);
 
        let ret = tmp;
 
        // Add current string to result of
        // other strings and check if
        // characters are unique or not
        for(let i = 0; i < tmp.length; i++)
        {
            let test = tmp[i] + arr[ind];
 
            if (check(test))
                ret.push(test);
        }
        return ret;
    }
 
    // Function to find the maximum
    // possible length of a string
    function maxLength(arr)
    {
        let tmp = helper(arr, 0);
 
        let len = 0;
 
        // Return max length possible
        for(let i = 0; i < tmp.length; i++)
        {
            len = len > tmp[i].length ? len : tmp[i].length;
        }
 
        // Return the answer
        return len;
    }
     
    let s = [];
    s.push("abcdefgh");
      
    document.write(maxLength(s));
 
// This code is contributed by suresh07.
</script>

8

Complejidad de Tiempo: O(2 ^N ) 
Espacio Auxiliar: O(N * 2 ^N )
 

Enfoque Eficiente (Usando Programación Dinámica): 

#include <bits/stdc++.h>
using namespace std;
 
int maxLength(vector<string>& A)
{
    vector<bitset<26> > dp
        = { bitset<26>() }; // auxiliary dp storage
    int res = 0; // will store number of unique chars in
                 // resultant string
    for (auto& s : A) {
        bitset<26> a; // used to track unique chars
        for (char c : s)
            a.set(c - 'a');
        int n = a.count();
        if (n < s.size())
            continue; // duplicate chars in current string
 
        for (int i = dp.size() - 1; i >= 0; --i) {
            bitset<26> c = dp[i];
            if ((c & a).any())
                continue; // if 1 or more char common
            dp.push_back(c | a); // valid concatenation
            res = max(res, (int)c.count() + n);
        }
    }
    return res;
}
 
int main()
{
    vector<string> v = { "ab", "cd", "ab" };
    int ans = maxLength(v);
    cout << ans; // resultant answer string : cfbdghzest
    return 0;
}

10

Complejidad de tiempo: O(N^2) 
Espacio auxiliar: O(N * 26)