Minimum length of string using chars appearing in a given string but not a substring of that string

Suppose we're given a string like "aabaccbbca", and want to find a short string that's not a substring of this string. However, we're limited to using the characters that appear in the string: in this case we can use 'a's, 'b's, and 'c's, but nothing else.

In that example case, there's no length-0, length-1, or length-2 solutions. There's lots of length-3 solutions. Actually, finding the minimum length is a lot more interesting than finding a specific solution.

So my question is: how can we efficiently compute the minimum length for which solutions exist to this 'find string with same alphabet that doesn't appear as a substring' problem?

Examples:

 minLengthMissingSubstring("") == 1
minLengthMissingSubstring("a") == 2
minLengthMissingSubstring("abc") == 2
minLengthMissingSubstring("aabaccbbca") == 3
minLengthMissingSubstring("abbaccbbca") == 2
minLengthMissingSubstring(
"0001002003004011012013014021022" +
"0230240310320330340410420430441" +
"1121131141221231241321331341421" +
"22423323424324433343444431442223") == 4

• What did you try? Where did you get stuck? Can you identify a conceptual problem that's stopping you answering this exercise on your own? – David Richerby Apr 6 '16 at 17:50
• I guess DP might work, since many of the sub-array/sequence problems could be solved with it. But I am stuck with the Bellman equation. – Joshua Apr 6 '16 at 17:58
• That title is incomprehensible. – Raphael Apr 7 '16 at 15:15
• Raphael is right ... at first, I disliked the problem. Then I realized the problem was interesting on its own and realized that my first impression was because of the title!! I upvoted the question (which had -1 at the time I upvoted) but I urge you Joshua to change the title to something more comprehensible – Carlos Linares López Apr 7 '16 at 15:21

$O(n \log_m n)$ solution, using a trie and a length cutoff

Relevant wikipedia articles: De Bruijn sequence, Trie

With an alphabet size of $m$, there are $m^t$ substrings of length $t$ that need to appear in a string in order to push the minimum missing substring length (our output) past $t$. But each character we add to a string can only eliminate one additional substring of length $t$. If our string is shorter than $m^t$, we know there must be a missing string of length $t$. This gives a bound on the length of the substrings we need to search in terms of the input string's size.

We know the input size $n$ and we know the alphabet size $m$, but we don't know our output value $t$. However, we know that $t$ must satisfy $m^t \leq n$. Re-arranging, we find that $t \leq \log_m n$. So we can use $t_{\text{cutoff}} = \lceil\log_m n\rceil$.

To make it easy to look for missing strings, we're going to insert every substring, up to the cutoff length, into a trie:

def buildTrie(text, cutoff):
root = TrieNode()
trail = [root]
for c in text:
newTrail = [root]
for t in trail:
t[c] = t[c] or TrieNode()
trail = newTrail[:min(len(newTrail), cutoff - 1)]
return root


The above function takes $O(\text{len}(\text{text}) \cdot \text{cutoff})$ time to finish, which in our case is $O(n \log_m n)$.

With our truncated trie in hand, we search through it for holes corresponding to missing substrings:

def firstLevelWithHole(trieNode, alphabet):
if trieNode is None: return 0
return 1 + min(firstLevelWithHole(trieNode[c], alphabet) for c in alphabet)


This search scans the whole trie. However, because the trie is cutoff at level $\log_m n$ and has fan-out at most $m$, we've done only $O(m^{\log_m n}) = O(n)$ work.

So our overall algorithm is:

def minMissingStringLength(text):
alphabet = new Set(text)
if len(alphabet) <= 1: return len(text) + 1
cutoff = math.ceil(math.log(len(text), len(alphabet)))
trie = buildTrie(text, cutoff)
return firstLevelWithHole(trie);


And it takes $O(n \log_m n)$ time and $O(n)$ space.

Notes

• The algorithm is easily tweaked to return a specific missing substring, instead of just the length.

• It's probably possible to reduce this to $O(n t)$ time by creating the trie in short-substring-first order, and scanning for holes before starting the next level.

• For truly huge alphabets, the dictionary lookups start costing $O(\lg m)$. I've omitted this cost from the analysis. Also you would want to modify the hole-finding to short-circuit instead of evaluating the whole tree, because it could add an $\Omega(m)$ cost otherwise.

• It's simpler to just use a rolling hash, after noticing that the answer is bounded by $log n$. You can also get $O(n log log n)$ by doing a binary search for the answer. – Mihai Apr 6 '16 at 20:07
• @MihaiCalancea Ah, good idea. There's $n$ strings of length $\log_m n$, so just put them into a set and count. But I think you're going to get an additional factor of $\log_m n$ due to having to try the shorter strings first. I also don't understand how you're going to hit $\log(\log(n))$ with a binary search, though. The sorting step involves $\log n$ scans. – Craig Gidney Apr 6 '16 at 20:16
• Hmm, I don't get what you're saying about trying shorter strings and I don't use any sorting. I'll go into a bit more details. I'm doing a binary search for the answer, in the idea that if our string contains all strings of length $len$ it also contains all strings of length $len - 1$. Thus we can only try $log(log n)$ values of $len$. For a fixed length, I only do one $O(n)$ scan, because you can compute the hash of substring $[i... i + len - 1]$ in O(1) time from the hash of $[i - 1... i + len]$, if you use a en.wikipedia.org/wiki/Rolling_hash. – Mihai Apr 7 '16 at 9:36
• @MihaiCalancea oh, you're talking about binary searching the length, with the rolling hash set thing as the comparator. Makes sense. Something about the hash function taking O(n) despite having non-constant sized elements bugs me though. Don't hash tables usually have some fixed percentage of collisions? We need to do comparisons whenever that happens. – Craig Gidney Apr 7 '16 at 12:45
• Generally when doing rolling hashes you just set the parameters right as to make the collision chance insignificant. But I was complicating things anyway. The "hash" can actually be a base $m$ number (which you also keep in a "rolling" manner) and you can just keep track of them in a frequency array. There are no collisions now. – Mihai Apr 7 '16 at 13:42