La string más pequeña que contiene todos los caracteres únicos de una array de strings dada

Dada una array de strings arr[] , la tarea es encontrar la string más pequeña que contenga todos los caracteres de la array de strings dada.

Ejemplos: 

Entrada: arr[] = {“su”, “usted”, “o”, “yo”}
Salida: ruyo
Explicación: La string “ruyo” es la string más pequeña que contiene todos los caracteres que se usan en todas las strings de la array dada. 

Entrada: arr[] = {“abm”, “bmt”, “cd”, “tca”}
Salida: abctdm

Enfoque: este problema se puede resolver utilizando la estructura de datos establecida . Set tiene la capacidad de eliminar duplicados, lo cual es necesario en este problema para minimizar el tamaño de la string . Agregue todos los caracteres del conjunto de todas las strings de la array arr[] y forme una string que contenga todos los caracteres restantes del conjunto, que es la respuesta requerida. 

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
string minSubstr(vector<string> s)
{
   
    // Stores the concatenated string
    // of all the given strings
    string str = "";
 
    // Loop to iterate through all
    // the given strings
    for (int i = 0; i < s.size(); i++)
    {
        str += s[i];
    }
 
    // Set to store the characters
    unordered_set<char> set;
 
    // Loop to iterate over all
    // the characters in str
    for (int i = 0; i < str.length(); i++)
    {
        set.insert(str[i]);
    }
    string res = "";
   
    // Loop to iterate over the set
    for (auto itr = set.begin(); itr != set.end(); itr++)
    {
        res = res + (*itr);
    }
 
    // Return Answer
    return res;
}
 
// Driver Code
int main()
{
    vector<string> arr = {"your", "you",
                          "or", "yo"};
 
    cout << (minSubstr(arr));
    return 0;
}
 
// This code is contributed by Potta Lokesh

import java.util.*;
 
public class GfG {
 
    public static String minSubstr(String s[])
    {
        // Stores the concatenated string
        // of all the given strings
        String str = "";
 
        // Loop to iterate through all
        // the given strings
        for (int i = 0; i < s.length; i++) {
            str += s[i];
        }
 
        // Set to store the characters
        Set<Character> set
            = new HashSet<Character>();
 
        // Loop to iterate over all
        // the characters in str
        for (int i = 0; i < str.length(); i++) {
            set.add(str.charAt(i));
        }
 
        // Stores the required answer
        String res = "";
        Iterator<Character> itr
            = set.iterator();
 
        // Loop to iterate over the set
        while (itr.hasNext()) {
            res += itr.next();
        }
 
        // Return Answer
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String arr[]
            = new String[] { "your", "you",
                             "or", "yo" };
 
        System.out.println(minSubstr(arr));
    }
}

# Python code for the above approach
def minSubstr(s):
 
    # Stores the concatenated string
    # of all the given strings
    str = ""
 
    # Loop to iterate through all
    # the given strings
    for i in range(len(s)):
        str += s[i]
 
    # Set to store the characters
    _set = set()
 
    # Loop to iterate over all
    # the characters in str
    for i in range(len(str)):
        _set.add(str[i])
 
    # Stores the required answer
    res = ""
 
    # Loop to iterate over the set
    for itr in _set:
        res += itr
 
    # Return Answer
    return res
 
# Driver Code
arr = ["your", "you", "or", "yo"]
print(minSubstr(arr))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
    public static string minSubstr(string []s)
    {
        // Stores the concatenated string
        // of all the given strings
        string str = "";
 
        // Loop to iterate through all
        // the given strings
        for (int i = 0; i < s.Length; i++) {
            str += s[i];
        }
 
        // Set to store the characters
        HashSet<char> set = new HashSet<char>();
 
        // Loop to iterate over all
        // the characters in str
        for (int i = 0; i < str.Length; i++) {
             
            set.Add(str[i]);
        }
 
        // Stores the required answer
        String res = "";
 
        // Loop to iterate over the set
        foreach(char i in set) {
            res += i;
        }
 
        // Return Answer
        return res;
    }
 
    // Driver Code
    public static void Main()
    {
        string []arr
            = { "your", "you", "or", "yo" };
 
        Console.WriteLine(minSubstr(arr));
    }
}
// This code is contributed by Samim Hossain Mondal.

  <script>
      // JavaScript code for the above approach
      function minSubstr(s)
      {
       
          // Stores the concatenated string
          // of all the given strings
          let str = "";
 
          // Loop to iterate through all
          // the given strings
          for (let i = 0; i < s.length; i++) {
              str += s[i];
          }
 
          // Set to store the characters
          let set = new Set();
 
          // Loop to iterate over all
          // the characters in str
          for (let i = 0; i < str.length; i++) {
              set.add(str[i]);
          }
 
          // Stores the required answer
          let res = "";
 
 
          // Loop to iterate over the set
          for (let itr of set) {
              res += itr;
          }
 
          // Return Answer
          return res;
      }
 
      // Driver Code
 
      let arr
          = ["your", "you",
              "or", "yo"];
 
      document.write(minSubstr(arr));
 
 
// This code is contributed by Potta Lokesh
  </script>

ruyo

Complejidad de tiempo: O(N*M), donde M es la longitud promedio de las strings en la array dada
Espacio auxiliar: O(1)