Sample good outputs:
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:
aabsince it is a substring of 3)
aaaabecause it is not minimal: we have other solutions with 3 characters only
- 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?
- Algorithm Request: "Shortest non-existing substring over given alphabet" seems to be the case for a single input string. If we can find a trivial reduction we can close as a duplicate.
for file uploads, browsers use the
enctype='multipart/form-data'encoding. This encoding can send several files in a single HTTP request. Files are sent directly without character encoding, so to separate the files, the browser has to find a string that is not contained in any of the files. I'd like to know how that can be done optimally. See also: https://stackoverflow.com/questions/4526273/what-does-enctype-multipart-form-data-mean/28380690#28380690
apparently this has some interest for bioinformatics, although I know nothing about that domain: https://biology.stackexchange.com/questions/3064/shortest-strings-not-present-in-the-human-genome . There has been some discussion on that question, but the answers there are more heuristic than algorithmic.