Maximize length of the String by concatenating characters from an Array of Strings

Last Updated : 22 Mar, 2023

Find the largest possible string of distinct characters formed using a combination of given strings. Any given string has to be chosen completely or not to be chosen at all.

Examples:

Input: strings ="abcd", "efgh", "efgh"
Output: 8
Explanation:
All possible combinations are {"", "abcd", "efgh", "abcdefgh"}.
Therefore, maximum length possible is 8.

Input: strings = "123467890"
Output: 10
Explanation:
All possible combinations are: "", "1234567890".
Therefore, the maximum length possible is 10.

Approach: The idea is to use Recursion.

Follow the steps below to solve the problem:

Iterate from left to right and consider every string as a possible starting substring.
Initialize a HashSet to store the distinct characters encountered so far.
Once a string is selected as starting substring, check for every remaining string, if it only contains characters which have not occurred before. Append this string as a substring to the current string being generated.
After performing the above steps, print the maximum length of a string that has been generated.

Below is the implementation of the above approach:

C++

// 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

// 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

# 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

JavaScript

<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>

Output

Time Complexity: O(2^N)
Auxiliary Space: O(N * 2^N)

Efficient Approach (Using Dynamic Programming):

C++

#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;
}

Java

import java.util.*;

public class Main {
    public static int maxLength(String[] A)
    {
        List<Set<Character> > dp
            = new ArrayList<>(Arrays.asList(
                new HashSet<>())); // auxiliary dp storage
        int res = 0; // will store number of unique chars in
                     // resultant string
        for (String s : A) {
            Set<Character> a = new HashSet<>();
            for (char c : s.toCharArray())
                a.add(c);
            if (a.size() < s.length())
                continue; // duplicate chars in current
                          // string

            for (int i = dp.size() - 1; i >= 0; --i) {
                Set<Character> c = new HashSet<>(dp.get(i));
                if (!Collections.disjoint(a, c))
                    continue; // if 1 or more char common
                dp.add(new HashSet<>(c));
                dp.get(dp.size() - 1)
                    .addAll(a); // valid concatenation
                res = Math.max(res, c.size() + a.size());
            }
        }
        return res;
    }

    public static void main(String[] args)
    {
        String[] v = { "ab", "cd", "ab" };
        int ans = maxLength(v);
        System.out.println(
            ans); // resultant answer string : cfbdghzest
    }
}

Python3

# Python program to implement the above approach
def maxLength(A):
    # Initialize an empty list to store bitsets (each representing a unique set of characters)
    # We start with an empty bitset, so that we can use it to compare with the incoming bitsets
    dp = [set()]  # auxiliary dp storage
    res = 0  # will store number of unique chars in
    # resultant string
    for s in A:
        a = set(s)  # used to track unique chars
        if len(a) < len(s):
            continue  # duplicate chars in current string

        for i in range(len(dp)-1, -1, -1):
            c = dp[i]
            if a & c:
                continue  # if 1 or more char common
            dp.append(c | a)  # valid concatenation
            res = max(res, len(c) + len(a))
    return res


v = ["ab", "cd", "ab"]
ans = maxLength(v)
print(ans)  

# Contributed by adityasha4x71

JavaScript

// javascript code implemementation 

function maxLength(A)
{
    let dp = new Array(26);
    for(let i = 0; i < 26; i++){
        dp[i] = new Array(26).fill(0); // auxiliary dp storage
    }

    let res = 0; // will store number of unique chars in
                 // resultant string

    for(let i = 0; i < A.length; i++){
        let s = A[i];
        
        let a = [];
        for(let j = 0; j < s.length; j++){
            a[s[j].charCodeAt(0) - 97] = "1";
        }
        
        let n = 0;
        for(let j = 0; j < a.length; j++){
            if(a[j] == "1") n = n + 1;
        }
        
        if(n < s.length) continue; // duplicate chars in current string
        
        for (let j = dp.length - 1; j >= 0; --j) {
            let c = dp[j];

            for(let k = 0; k < 26; k++){
                if(c[k] == "1" && a[k] == "1") continue; // if 1 or more char common
            }
            
            let temp = "";
            for(let k = 0; k < 26; k++){
                if(c[k] == "1" || a[k] == "1") temp = temp + "1";
                else temp = temp + "0";
            }
            dp.push(temp); // valid concatenation
            let c_count = 0;
            for(let k = 0; k < 26; k++){
                if(c[k] == "1") c_count++;
            }
            res = Math.max(res, c_count + n-2);
        }
    }

    return res;
}


let v = [ "ab", "cd", "ab" ];
let ans = maxLength(v);
console.log(ans); // resultant answer string : cfbdghzest

// The code is contributed by Arushi Jindal.

// C# code implemementation 
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

class HelloWorld {
    
    public static int maxLength(string[] A)
    {
        List<string> dp = new List<string> ();
        for(int i = 0; i < 26; i++){
            string temp = "";
            for(int j = 0; j < 26; j++){
                temp = temp + "0";
            }
            dp.Add(temp);
        }

        
        int res = 0; // will store number of unique chars in
                     // resultant string

        for(int i = 0; i < A.Length; i++){
            string s = A[i];
            List<char> a = new List<char>();
            for(int indx = 0; indx < 26; indx++){
                a.Add('0');
            }
            for(int j = 0; j < s.Length; j++){
                a[System.Convert.ToInt32(s[j]) - 97] = '1';
            }

            int n = 0;
            for(int j = 0; j < a.Count; j++){
                if(a[j] == '1') n = n + 1;
            }

            if(n < s.Length) continue; // duplicate chars in current string

            for (int j = dp.Count - 1; j >= 0; --j) {
                string c = dp[j];

                for(int k = 0; k < 26; k++){
                    if(c[k] == '1' && a[k] == '1') continue; // if 1 or more char common
                }

                string temp = "";
                for(int k = 0; k < 26; k++){
                    if(c[k] == '1' || a[k] == '1') temp = temp + "1";
                    else temp = temp + "0";
                }
                dp.Add(temp); // valid concatenation
                int c_count = 0;
                for(int k = 0; k < 26; k++){
                    if(c[k] == '1') c_count++;
                }
                res = Math.Max(res, c_count + n-2);
            }
        }

        return res;
    }
    static void Main() {
        string[] v = {"ab", "cd", "ab"};
        int ans = maxLength(v);
        Console.WriteLine(ans); // resultant answer string : cfbdghzest
    }
}

// The code is contributed by Nidhi goel.

Output

Time Complexity: O(N^2)
Auxiliary Space: O(N * 26)

Maximize product of lengths of strings having no common characters

rishabhtyagi2306

Improve

Article Tags :

Practice Tags :

Maximize length of the String by concatenating characters from an Array of Strings

Similar Reads

Thank You!

What kind of Experience do you want to share?