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

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

• You will find a very helpful similarity in a question that has already been answered: cs.stackexchange.com/questions/21896/… – Francesco Gramano Feb 22 '15 at 22:38
• @FrancescoGramano thanks! That is indeed the case for one sequence. – Ciro Santilli 新疆改造中心 六四事件 法轮功 Feb 23 '15 at 6:55
• Note that the other question deals with substrings, a different problem. – Raphael Feb 23 '15 at 7:53
• @Raphael I don't quite understand, is it because there is a difference between substrings and subsequences? Or something else? – Ciro Santilli 新疆改造中心 六四事件 法轮功 Feb 23 '15 at 8:02
• @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. – babou Feb 23 '15 at 14:22

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