Minimum length of string using chars appearing in a given string but not a substring of that string
$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()
            newTrail.add(t[c])
        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) &lt;= 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.