6
$\begingroup$

Alphabet: abc

Sample input:

  1. abc
  2. cba
  3. aabbcc
  4. aaabbbccc
  5. caac

Sample good outputs: acb, cab, cac and others, since they are not substrings of any other, and because all strings of length 1 and 2 are present.

Sample bad outputs:

  • aab since it is a substring of 3)
  • aaaa because it is not minimal: we have other solutions with 3 characters only

Questions:

  • What are the best ways to solve it?
  • Does the problem have a well known coined name?
  • What is the complexity of the calculation in terms of the input size (number of strings N and maximum string length M)?
  • What is the average asymptotic size of the output considering random uniformly distributed inputs?

Related questions:

Applications:

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ You will find a very helpful similarity in a question that has already been answered: cs.stackexchange.com/questions/21896/… $\endgroup$
    – Francesco Gramano
    Feb 22, 2015 at 22:38
  • $\begingroup$ @FrancescoGramano thanks! That is indeed the case for one sequence. $\endgroup$
    – Ciro Santilli OurBigBook.com
    Feb 23, 2015 at 6:55
  • $\begingroup$ Note that the other question deals with substrings, a different problem. $\endgroup$
    – Raphael ♦
    Feb 23, 2015 at 7:53
  • 1
    $\begingroup$ @Raphael Interestingly, the OP gives examples that are good for substrings and subsequences, as far as I can see. Except for the fact that the third answer $aac$ is wrong in both cases since it occurs in string 5. So the OP should make it clear whether he actually mean subsequence, i.e. composed of characters of a string in the right order, but not necessarily contiguous. I somehow doubt it, since the question says a sub-sequence of a set of sequences rather than a sub-sequence of a set of strings as it should if he made the proper distinction. $\endgroup$
    – babou
    Feb 23, 2015 at 14:22
  • 1
    $\begingroup$ Ahhh, we have multiple strings here, sorry. Well, my second answer applies gracefully to multiple input strings. Suffix trees don't really care from how many strings the suffices come. $\endgroup$
    – Raphael ♦
    Feb 23, 2015 at 22:21

1 Answer 1

Reset to default
2
$\begingroup$

Here's one possible solution, similar to the linked question: Algorithm Request: “Shortest non-existing substring over given alphabet”

Use a sliding window over each input string to build your trie.

  • For n=1 to n=max(length(s)) where s is an input string, do:
  • For each s, construct window of size n, slide window over s adding each window (substring of size n) to the trie, then
  • Visit each parent of the leaf set of the trie. If there exists a parent node whose set of child nodes is smaller than the size of the alphabet, then you can form your desired string from this parent by appending a character from the alphabet that does not result in a string identical to one of the leaf nodes
  • If no such parent node exists, continue to next larger n
Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.