2
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – David Richerby Apr 6 '16 at 17:50
  • $\begingroup$ 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. $\endgroup$ – Joshua Apr 6 '16 at 17:58
  • $\begingroup$ That title is incomprehensible. $\endgroup$ – Raphael Apr 7 '16 at 15:15
  • $\begingroup$ 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 $\endgroup$ – Carlos Linares López Apr 7 '16 at 15:21
3
$\begingroup$

$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) <= 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mihai Apr 6 '16 at 20:07
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney Apr 6 '16 at 20:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Mihai Apr 7 '16 at 9:36
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney Apr 7 '16 at 12:45
  • $\begingroup$ 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. $\endgroup$ – Mihai Apr 7 '16 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.