Find the shortest string that is not a sub-string of a set of strings [duplicate]

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.

• 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:

• You will find a very helpful similarity in a question that has already been answered: cs.stackexchange.com/questions/21896/… Commented Feb 22, 2015 at 22:38
• @FrancescoGramano thanks! That is indeed the case for one sequence. Commented Feb 23, 2015 at 6:55
• Note that the other question deals with substrings, a different problem. Commented Feb 23, 2015 at 7:53
• @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. Commented Feb 23, 2015 at 14:22
• 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. Commented Feb 23, 2015 at 22:21

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