2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ It's best that you update the question with all the necessary details. Also include what you have tried so far. $\endgroup$
    – Russel
    May 8 at 13:02
  • $\begingroup$ @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. $\endgroup$
    – John L.
    May 8 at 15:17
  • 1
    $\begingroup$ If the length is fixed, the "shortest" available word makes little sense. And in any case, the "available word" is probably not unique. $\endgroup$ May 9 at 14:10

1 Answer 1

3
$\begingroup$

Link shorteners don't face this problem. When they generate a word for you, they use a fixed-length words, so it suffices to keep a dictionary of all words that are currently in use. Also most words are not in use, so for their purpose it suffices for them to pick a random word, check that it is not in use, and if it is, repeat.

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.

$\endgroup$
1
  • $\begingroup$ @KellyBundy, oops. Thank you, you have spotted a problem in my answer. See updated answer for perhaps a better solution. $\endgroup$
    – D.W.
    May 10 at 4:45

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.