I'm looking for an (efficient) algorithm to solve the following problem:

Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not contained in $S$.

Try as I might, I can't seem to map this problem to any of the standard CS string problems.

  • $\begingroup$ What specifically have you tried? $\endgroup$
    – Raphael
    Feb 22 '14 at 9:25
  • $\begingroup$ I don't know what you mean by "standard CS string problems", but modern stringology uses suffix trees/arrays as a basic primitive, since they can be constructed in linear time using linear space. (If you are using suffix arrays, you'll need the lca array too.) Once you know that, you should be able to solve the problem in linear time. (As a further hint, if there is a character in $M$ that is not in $S$, then a one-character string is a valid answer to the question.) $\endgroup$
    – Pseudonym
    Feb 23 '14 at 10:12
  • $\begingroup$ Incidentally, compare with this question on SE. stackoverflow.com/questions/12607512/… $\endgroup$
    – Pseudonym
    Feb 23 '14 at 13:15

Here is the clean presentation (after going in circles around it).

First you consider all substrings of S that are in M*. From that you build a trie, which may be understood as a tree structured FA that recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from which there is no arc for a given character in M, you have your answer which is the string associated with that node concatenated with the missing character. Complexity is $O(n^2)$ where $n$ is the length of the string S, because that is the maximum number of characters you may have to consider while building the trie.

Note regarding complexity: In the trie construction you have to consider only the longest substring in $M^*$ starting at each position in $S$, since shorter ones are automatically taken care of. Each state thus created is an accepting state recognizing one substring. There are at most $n$ substrings in $M^*$, each having at most $n$ characters. Each is considered in constant time.

  • $\begingroup$ Looks like that might work indeed. Complexity should be dominated by a term linear in the length of the string. Sounds mighty hard to implement though... $\endgroup$ Feb 21 '14 at 19:11
  • $\begingroup$ Not too hard. Everything is easy and fast, except the building of the initial automaton. This requires a bit of thinking if you want to do it fast. $\endgroup$
    – babou
    Feb 21 '14 at 19:13
  • $\begingroup$ I definitely like the idea (sorry, can't upvote yet, requires 15 reputation). I'd still like to hear alternative approaches, though. $\endgroup$ Feb 21 '14 at 19:20
  • $\begingroup$ Actually, the building of the initial FA isn't the problem. It's a simple matter build a FA with $|\;S\;|$ states that will accept all the substrings of $S$. The problem is that you might wind up with a nondeterministic FA. There's a simple construction to go from a deterministic FA to a FA that accepts the complement of the first one, but I don't know of any easy way to do that before first making the FA deterministic. Unfortunately a NFA with $n$ states might require $O(2^n)$ states in its deterministic equivalent, which kills your complexity. $\endgroup$ Feb 21 '14 at 19:24
  • $\begingroup$ Uuhh... that's not what I want then. $\endgroup$ Feb 21 '14 at 19:29

Here's another approach that takes only linear time.

  1. Construct a suffix tree for $S$ (and alphabet $M$).
  2. Perform a breadth-first traversal and stop at the first missing edge or non-singleton label $ab\dots$ (if there is no missing edge on that level).
  3. The path from the root to (and including the) missing edge resp. $ax$ with $x \neq b$ is your result.

This is correct since every substring of $S$ is the label sequence of some path from the root downwards, and breadth-first traversal finds the shortest sequence that does not label such a path.

Regarding the non-singleton labels, if such label $ab\dots$ exists there was no continuation of the current substring other than $ab$, so $\dots ax$ is indeed not a substring. If there was no missing edge on the level of the non-singleton label, the resulting string is as long as any we can find on the next level, so it's shortest.

Using Ukkonen's algorithm, step 1 takes linear time (assuming $M$ is fixed) and the result is a tree of linear size. Therefore, step 2 runs in linear time as well, and 3 three clearly does, too.

  • $\begingroup$ FWIW, this nicely extends to sets of strings; just build the suffix tree for the whole set. $\endgroup$
    – Raphael
    Feb 23 '15 at 11:13
  • $\begingroup$ Why the downvote? Did I make a mistake? If not, this is by far the most efficient approach presented here. $\endgroup$
    – Raphael
    Mar 18 '15 at 16:07

Let $n = |w|$ and $m = |\Sigma|$, where $w$ is the input string and $\Sigma$ is the input alphabet. There are $n - k + 1$ substrings of $w$ of length $k$, and $m^k$ strings over $\Sigma$ of length $k$. If $n - k + 1 < m^k$ then, by the pigeonhole principle, there must be a string over $\Sigma$ of length $k$ that is not a substring of $w$.

There are on the order of $m^i$ strings of length less than $i$ over $\Sigma$. Determining whether an arbitrary string is a substring of $w$ can be done in time $n$. Thus we have, at most, $nm^i$ work to do, where $i = k + 1$ in the worst case. We can extrapolate from the inequality that $n < m^k$, so $k > \log_m n$; so $k = 1 + \log_m n$ always works. Note: if we can rule out $k = 1$, we can go even further and let $k = \log_m n$.

Taken altogether, this means that the total amount of work that the naïve method (enumerate strings in lexicographic order, and check the input for each string over $\Sigma^*$ until you find one that's missing) would never do more than $O(n^2m^2)$ (*fixed an algebraic mistake; had $O(n^3m)$ previously, but should have been $O(n^2m^2)$) work in the worst case, although this bound may not be tight. Note that if we rule out $k = 1$ and take $k = \log_m n$, we lose an $n$ and get $O(n^2m)$.

  • $\begingroup$ Hmm... if the size of the dictionary (example) is 1 MB and $m = 26$, $O(n^3m)$ sounds a bit less than practical, though of course the actual work might be less in that case :) $\endgroup$ Feb 21 '14 at 19:40
  • $\begingroup$ @user232362636 Agreed... it's worth pointing out that the number of words of length less than $i$ is really closer to $\frac{m^i}{m-1} + m$, so the $m$ term ends up going away, and we're left with something more like $O(n^3)$. Still, it's always nice when you can not only clearly state an effective computation for something, but that computation turns out to be a relatively straightforward polynomial. $\endgroup$
    – Patrick87
    Feb 21 '14 at 19:45
  • $\begingroup$ @user232362636 Take another look at my post; I fixed an algebraic mistake, so the complexity from the original argument should have been $O(n^2m^2)$ originally. I also realized that in most cases ($n$ greater than $m$, particularly) we can always choose a smaller value for $k$, reducing the overall complexity to $O(n^2m)$; the real answer might even be something closer to $O(n^2)$, based on the above comment (which still applies). It might be a fun exercise for you to implement brute-force search to see if this algorithm or babou's performs better. $\endgroup$
    – Patrick87
    Feb 21 '14 at 20:41
  • $\begingroup$ Thanks, that's exactly what I'll do (first I have to implement babou's solution though, which will be more difficult than yours though it feels cleaner). $\endgroup$ Feb 21 '14 at 21:56
  • $\begingroup$ Though this isn't definitely going to find the shortest non existent substring, though you can assert that the shortest non existent substring is of length k or shorter. $\endgroup$
    – gryftir
    Apr 12 '14 at 3:01

Here is another approach that is conceptually simple (you are asking for "standard string problems").

  1. Construct an NFA $A$ for $M^*$ (two states).
  2. Construct an NFA $B$ for $\{ w \mid vwx = S; v,w,x \in \Sigma^* \}$ ($n+2$ states).
  3. Compute $\overline{B}$.
  4. Compute $\overline{B} \cap A$.
  5. Find a shortest path from the starting state to a final state (breadth-first search). The traversed edges make up your solution.

Per se, the time for 3. might be huge (and then also 4.) since inverting NFA takes exponential time in the worst case.


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.