# Shortest word not in dynamic set

What is the most efficient data structure for a dynamic set of words over a finite alphabet $$\Sigma$$ which supports the following operations?

• Add a word.
• Remove a word.
• Determine a shortest word which is not in the set.

Does it help if all words have the same length?

A real world example: I was thinking about link shorteners (e.g. https://bitly.com/) and how they search for available short codes.

• It's best that you update the question with all the necessary details. Also include what you have tried so far. May 8 at 13:02
• @cupcakearmy Comments on this site are considered as temporary "Post-It" notes left on a question or answer. That is why we ask you to update the question. May 8 at 15:17
• If the length is fixed, the "shortest" available word makes little sense. And in any case, the "available word" is probably not unique. May 9 at 14:10

If you actually needed to face this problem, probably a reasonable approach is to have a separate dictionary for each length, where the dictionary for length $$\ell$$ keeps track of the words of length $$\ell$$. Each dictionary could be stored, for instance, as a trie (where each node of the trie is augmented with the number of leafs found underneath that node); then it is easy to find a word that is not in the dictionary in $$O(\ell)$$ time. You can also keep track of all lengths that are missing at least one word, in a self-balancing binary tree, which makes it easy to find in logarithmic time the length of a shortest word that is not in the set (I recommend you maintain a pointer from each dictionary to its corresponding leaf in this tree, and vice versa). Putting all of this together, all operations can be implemented in $$O(\ell)$$ time, plus a term that is logarithmic in the total number of different lengths.