# Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with.

I have a set of strings, for example:

"my name is john",
"i like cheese",
"the cheese is in the kitchen",
"john likes cheese"


Let $$S$$ be union of all words appearing in the previous strings. my,name,is,john,i,like,cheese,what,your,the,in,kitchen,likes

The problem seeks an optimal combination of words, that construct the maximum number of strings from the initial set, under the following conditions :

• Words are separated by a comma.
• The sum of the lengths of selected words is bounded by a constant number (say 25).
• A sting can be rebuilt only if all words occurring in this string are contained in the selected combination.

For example, the combination john,cheese,like,likes,i uses 24 characters and allows to rebuild both "i like cheese" and "john likes cheese".

Here is what I have tried to implement.

First, I sort every single word by the number of strings it's contained in. In this example:

is      (3)
cheese  (3)
john    (2)
name    (2)
my      (1)
i       (1)
like    (1)
what    (1)
...


So I'm now using this array: [is, cheese, john, name, my, i, like, ...], let us call it initial_array

And here is the idea of the algorithm I amm using. First, I initialize another array of strings containin of all the strings g the first word from initial_array, let's call it new_array:

[is]

Then, while the total length of all the strings of new_array plus the commas does not exceed the limit of 25 chars, I append them:

[is,cheese] (9)
[is,cheese,john] (14)
[is,cheese,john,name] (19)
[is,cheese,john,name,my] (22)
[is,cheese,john,name,my,i] (24) --> best potential combination so far, can rebuild 1 string: "my name is john"
[is,cheese,john,name,my,i,like] (29) --> up to 25 chars


When I reach a length up to 25 chars, I try to replace the last element of new_array by the following of initial_array:

[is,cheese,john,name,my,i,what] (29) --> up to 25 chars
[is,cheese,john,name,my,i,your] (29) --> up to 25 chars
...


And when I reach the last word of initial_array, I remove it from new_array and replace the previous one by the next one of initial_array:

// if the last word of initial_array is "likes"
[is,cheese,john,name,my,i,likes] --> we reached the last word
[is,cheese,john,name,my,like]
[is,cheese,john,name,my,like,what]
etc...


If this solution allows me to try all the possible combinations without repetitions, the running time increases exponentially as words are being added to the initial_array, and quickly becomes unusable. So I am looking for a better idea to improve this algorithm.

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $$k$$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $$k$$ letters and hence have union at most $$k$$. This problem is very similar to the NP-hard minimum $$k$$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information).
• ETH is a stronger hypothese than P$\neq$NP. If P=NP (which is probably not) then ETH does not make sense, since 3-SAT would have a polynomial algorithm. However, ETH and SETH are useful to prove a lower-bound on the exponent (SETH for lower-bounds on the constant factor of the exponent). On the other hand proving NP-hardness is enough to prove that exponential running time is the best we can hope for assuming P$\neq$NP which is a precondition for ETH and SETH – narek Bojikian Nov 13 '19 at 11:45