# 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/… Feb 22, 2015 at 22:38
• @FrancescoGramano thanks! That is indeed the case for one sequence. Feb 23, 2015 at 6:55
• Note that the other question deals with substrings, a different problem.
– Raphael
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. 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.
– Raphael
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