Как найти слово, гарантированно отсутствующее в наборе?
=========================================================

 Есть некий алфавит — например, A..Z.  

Есть набор слов из этого алфавита.  

Придумать слово из этого алфавита, отвечающее двум требованиям.  

1. Не очень длинное.  

2. Отсутствует в наборе.  

Какие есть соображения? 

 Придумал, причём тупо. Комбинаторикой высчитываем, какой длины (по принципу Дирихле) должно быть наше слово: например, если у нас цифры от 0 до 9 и 125 строк, достаточно взять трёхзначные. Вот мы берём 126 битов (ну или 128 для круглого счёта), из наших чисел берём только трёхзначные и начинаем заполнять биты. Есть, например, 025 — вот в 25-й бит и суём единичку. После этого остаётся найти в битовой маске ноль и преобразовать в нашу строку: на 45-м месте — значит, 045. 

 - хранить набор слов или в **hashset** или в **trie**  

- выбирая хранения в префиксном дереве, далее генерируешь рандомно длину, далее идешь в глубь по уровням, стараясь или уйти от существующих ключей или останавливаясь на определенном уровне, который образует слово, но которое еще не записано в дереве  

  

**a-n-c-h-o-r** допустим это одна из ветвей дерева, во главе с буквой "а", ты можешь дойти до буквы "о" и, поняв, что такого слова еще нет "ancho" вернуть его как результат 

 Еще есть вариант (если у вас все слова разные) - подсчитайте сколько раз каждая длина встречается в наборе.  

  

Если вы видите, что у вас однобуквенных слов меньше, чем букв в алфавите - то можно выдать однобуквенное слово. Иначе, если двух-буквенных слов меньше |alphabet|^2, то можно выдать двубуквенное слово. И так далее. Вот нашли вы минимальную длину.   

  

Чтобы найти и само слово, заведите битмап размером со сколько у вас слов. Потом пройдитесь по словам и если слово нужной длины, поставьте 1 в битмапе с номером равным строке, если ее интерпретировать как число в |alphabet|-ой системе счисления (самый младший символ равен цифре 0). Если число переваливает за размер битмапы, то можно текущую строку проигнорировать. Потом найдите любой 0 бит в битмапе. Его номер переведите назад в |alphabet| систему счисления.  

  

Пример. Алфавит - {a,b}. Слова: "a", "b", "aa", "ab", "bb".  

  

Мы видим 2 однобуквенных слова. Никак. 3 двухбуквенных, но 3 < 2^2 - значит можно выдать двубуквенную строку.  

  

У нас 2 символа в алфавите, интерпретируем a=0, b=1. "aa" = 0, "ab" = 1, "bb" =3. В битмапе останется пустым индекс 2. Это 10 в двоичной системе или "ba" в строках - это и есть ответ. Да еще и лексикографически минимальный.  

  

Если слова могут повторятся, то можно чуть изменить решение: точно также перенумеруйте все возможные слова в вашем алфавите. Сначала будут однобуквенные, потом двубуквенные и т.д. При переводе строки в индекс - также переводите из |alphabet|-ичной системы счисления. Но для слова из l символов прибавляйте смещение |alphabet|^(l-1)+|alphabet|^(l-2)+... |alphabet|^1. Точно так же, если в процессе вычисления видно, что индекс не поместится в битмапу (больше количества строк), то можно забить на эту строку. Поэтому же можно сразу пропускать слишком длинные слова.  

  

Опять же, помечайте бит в битмапе. Потом найдите первый нулевой бит. И назад преобразуйте в строку - сначала найдите смещение (суммируйте степени |alphabet|, пока они не перевалят за текущий индекс). Так вы поймете, сколько символов у вас в строке. Вычтите смещение и переводите индекс в |alphabet|-ичную систему счисления.  

  

Этот вариант в среднем может работать чуть дольше, но все так же очень быстро.  

  

Еще, оба эти варианта самые экономные по памяти. 

[https://ru.wikipedia.org/wiki/Фильтр\_Блума](https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D1%8C%D1%82%D1%80_%D0%91%D0%BB%D1%83%D0%BC%D0%B0) 
> — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая проверять принадлежность элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.