I wanna understand how Can I do this: I am given an array of strings in python such as:

Array1 = [‘co’, ‘dil’, ‘ity’]
enter code here

I am trying to make a function which should calculate the length of the longest string S such that: S is a concatenation of some of the strings from A and every letter in S is different. Example: Given A = ['co’, ’dil', ’ity’]. The function should return 5. The resulting string S could be "codil", "dilco", "coity" or "Ityco".

CodePudding user response：

Let's say that each word in the Array1 is a verticle in a graph. One node is connected to another node if the two corresponding words have no common letters. Each node has a weight that equals the length of the word. Now the problem transforms into the following: find the maximum (by weight) clique (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. This is a well-known NP-complete problem (https://en.wikipedia.org/wiki/Clique_problem), which has no efficient solution:

To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices. Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute-force search are known. For instance, the Bron–Kerbosch algorithm can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique.

CodePudding user response：

A basic idea can be the following one:

1. you iterate over Array1 and, for each string1 you loop over the other strings (string2) in the array;
2. looping over the characters of the string1, you look if the string1 has a character in common with every other string2, if not so you calculate the sum of the two string lengths and you merge the two strings;
3. now you do the step 2. but you have the merged string instead of string1 and you proceed to confront the merged string with the others;
4. you find the maximum of every sum.

An example function doing that (not necessarily the best one) could be the following:

def lenght_longest_string(Array1):
    max = 0
    
    for string1 in Array1:
        tmp = len(string1)
        
        for string2 in Array1:
            if string1 != string2:
                isGood = True
                for char in string1:
                    if char in string2:
                        isGood = False
                        
                if isGood == True:
                    string1 = string1   string2
                    tmp = tmp   len(string2)

        if tmp > max:
            max = tmp
            
    return max

I assume that you only need to return the length of the concatenated string S.