2
$\begingroup$

This question already has an answer here:

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:

$\endgroup$

marked as duplicate by Raphael Feb 23 '15 at 17:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 '15 at 22:38
  • $\begingroup$ @FrancescoGramano thanks! That is indeed the case for one sequence. $\endgroup$ – Ciro Santilli 新疆改造中心996ICU六四事件 Feb 23 '15 at 6:55
  • $\begingroup$ Note that the other question deals with substrings, a different problem. $\endgroup$ – Raphael Feb 23 '15 at 7:53
  • $\begingroup$ @Raphael I don't quite understand, is it because there is a difference between substrings and subsequences? Or something else? $\endgroup$ – Ciro Santilli 新疆改造中心996ICU六四事件 Feb 23 '15 at 8:02
  • 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 '15 at 14:22
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
$\endgroup$

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