Open In App

Smallest string containing all unique characters from given array of strings

Last Updated : 17 Feb, 2023
Comments
Improve
Suggest changes
Like Article
Like
Report

Given an array of strings arr[], the task is to find the smallest string which contains all the characters of the given array of strings.

Examples: 

Input: arr[] = {"your", "you", "or", "yo"}
Output: ruyo
Explanation: The string "ruyo" is the smallest string which contains all the characters that are used across all the strings of the given array. 

Input: arr[] = {"abm", "bmt", "cd", "tca"}
Output: abctdm

Approach: This problem can be solved by using the Set Data Structure. Set has the capability to remove duplicates, which is needed in this problem in order to minimize the string size. Add all the characters in the set from all the strings in the array arr[] and form a string containing all the characters remaining in the set, which is the required answer. 

Below is the implementation of the above approach.

C++ 
// 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
Java 
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));
    }
}
Python3 
# 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# 
// 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.
JavaScript 
    <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>

Output
ruoy

 Time Complexity: O(N*M), where M is the average length of strings in the given array
Auxiliary Space: O(N) because extra space for string str is being used

Approach #2: This problem can also be solved by using the Map Data Structure. Map stores all the characters present in the string with their occurrence. After iterating on the map we will get the all unique characters.

C++ 
// 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];
    }

    // map to store the characters with frequency
    unordered_map<char, int> mp;

    // Loop to iterate over all
    // the characters in str
    for (int i = 0; i < str.length(); i++) {
        mp[str[i]]++;
    }
    string res = "";

    // Loop to iterate over the map
    for (auto it : mp) {
        res += it.first;
    }

    // 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 Prasad Kandekar(prasad264)
Java 
// Java code for the above approach
import java.util.*;
class GFG {
  public static String minSubstr(List<String> s)
  {

    // Stores the concatenated string
    // of all the given strings
    String str = "";

    // Loop to iterate through all
    // the given strings
    for (String x : s) {
      str += x;
    }

    // map to store the characters with frequency
    Map<Character, Integer> mp = new HashMap<>();

    // Loop to iterate over all
    // the characters in str
    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      if (mp.containsKey(c)) {
        mp.put(c, mp.get(c) + 1);
      }
      else {
        mp.put(c, 1);
      }
    }

    StringBuilder res = new StringBuilder();

    // Loop to iterate over the map
    for (Map.Entry<Character, Integer> entry :
         mp.entrySet()) {
      res.append(entry.getKey());
    }

    // Return Answer
    return res.toString();
  }

  // Driver Code
  public static void main(String[] args)
  {
    List<String> arr
      = Arrays.asList("your", "you", "or", "yo");
    System.out.println(minSubstr(arr));
  }
}

// This code is contributed by Prasad Kandekar(prasad264)
Python3 
# Python code for the above approach

def min_substr(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]

    # dictionary to store the characters with frequency
    mp = {}

    # Loop to iterate over all
    # the characters in str
    for i in range(len(str)):
        if str[i] in mp:
            mp[str[i]] += 1
        else:
            mp[str[i]] = 1

    res = ""

    # Loop to iterate over the map
    for key in mp:
        res += key

    # Return Answer
    return res

# Driver Code
arr = ["your", "you", "or", "yo"]
print(min_substr(arr))

# This code is contributed by karthik
C# 
// C# code for the above approach
using System;
using System.Collections.Generic;

public class GFG {
  static string MinSubstr(List<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.Count; i++) {
      str += s[i];
    }

    // dictionary to store the characters with frequency
    Dictionary<char, int> mp
      = new Dictionary<char, int>();

    // Loop to iterate over all
    // the characters in str
    for (int i = 0; i < str.Length; i++) {
      if (mp.ContainsKey(str[i])) {
        mp[str[i]]++;
      }
      else {
        mp[str[i]] = 1;
      }
    }

    string res = "";

    // Loop to iterate over the map
    foreach(var item in mp) { res += item.Key; }

    // Return Answer
    return res;
  }

  // Driver Code
  static public void Main(string[] args)
  {
    List<string> arr = new List<string>() {
      "your", "you", "or", "yo"
      };

    Console.WriteLine(MinSubstr(arr));
  }
}

// This code is contributed by Prasad Kandekar(prasad264)
JavaScript 
// JavaScript code for the above approach
function minSubstr(s) {

    // Stores the concatenated string 
    // of all the given strings
    var str = "";

    // Loop to iterate through 
    // all the given strings
    for (var i = 0; i < s.length; i++) {
        str += s[i];
    }

    // map to store the characters with frequency
    var mp = new Map();
    
    // Loop to iterate over all 
    // the characters in str
    for (var i = 0; i < str.length; i++) {
        if (mp.has(str[i])) {
            mp.set(str[i], mp.get(str[i]) + 1);
        }
        else {
            mp.set(str[i], 1);
        }
    }

    var res = "";

    // Loop to iterate over the map
    for (var [key, value] of mp) {
        res += key;
    }

    // Return Answer
    return res;
}

// Driver Code
var arr = ["your", "you", "or", "yo"];
console.log(minSubstr(arr));

// This code is contributed by Prasad Kandekar(prasad264)

Output:

ruoy

Complexity analysis:

Time Complexity: O(N*M), where M is the average length of strings in the given array
Auxiliary Space: O(N) because extra space for string str and unordered_map are being used


Next Article
Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, ...

A
akshitsaxenaa09
Improve
Article Tags :
Practice Tags :

Similar Reads

We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox