I am looking for a solution to this problem: Given multiple sets of letters (Set0={a,b,c,d}, Set1={d,e,f,g}, Set2={a,b,e,g}, ...), what is the minimal length of the string containing all the sets. The sets have to be present as one substring, it is possible to duplicate letters in the final string, and it is also possible to permutate letters in one set.


abc|def|gabe (strlen = 10, sets are like: Set0, Set1, Set2)

Where the Set0 is starting at the index 0, Set1 is starting at the index 3, Set2 is starting at the index 7.

Another better solution is:

ab|egf|dabc (strlen = 9, sets are like: Set2, Set1, Set0)

Where the Set0 is starting at the index 5, Set1 is starting at the index 2, Set2 is starting at the index 0.

  • $\begingroup$ This problem looks like a variant of the shortest common superstring problem. To be clear, is any permutation of the strings allowed? $\endgroup$ – Discrete lizard Apr 26 '19 at 15:27
  • $\begingroup$ And @Discretelizard you can permute the Sets, the final string can be Set0, Set2, Set1 for instance $\endgroup$ – J.Doe Apr 26 '19 at 15:31
  • 1
    $\begingroup$ Is this re-phrasal of your problem correct? Given $n$ sets of characters, find a string $s$ such that for each set there is a substring of $s$ containing those, and only those characters. This is assuming sets can overlap, so if the sets are $\{a, c\}$ and $\{a, b\}$ then $cab$ would be a string that solves it. $\endgroup$ – orlp Apr 26 '19 at 15:34
  • $\begingroup$ @orlp Yes, plus you can have duplicated letters, so one of the best solution for {a,b,c}, {b,c,d} and {c,d,a} would be "abcda" $\endgroup$ – J.Doe Apr 26 '19 at 15:37
  • $\begingroup$ @J.Doe If set0={a} and set1={a}, do we need that the letter a appears twice in the superstring? Or is it guaranteed that the initial sets are different? $\endgroup$ – John L. Apr 26 '19 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.