Эффективный алгоритм поиска наименьших панграмматических окон?

Панграмматическое окно— это подстрока большего фрагмента текста, содержащая все 26 букв алфавита. Приведу пример из Википедии, учитывая этот текст:

Я пел, и мне казалось, что я пел очень хорошо; но он только взглянул мне в лицо с очень насмешливым выражением и сказал: «Как долго вы поете, мадемуазель?»

Самое маленькое панграмматическое окно в тексте — это строка:

g very well; но он только взглянул мне в лицо с очень насмешливым выражением

, Которое действительно содержит каждую букву по крайней мере один раз.

Мой вопрос заключается в следующем.:Учитывая текстовый корпус, каков наиболее эффективный алгоритм для нахождения наименьшего панграмматического окна в тексте?

Я немного подумал и уже придумал следующие алгоритмы. У меня есть сильное ощущение, что они не оптимальны, но я решил опубликовать их в качестве отправной точки.

Существует простой наивный алгоритм, работающий за время O (n ²)и пространство O (1 ):Для каждой позиции в строкепросканируйте вперед от этой позиции и отследите, какие буквы вы видели (, возможно, в битовом векторе, который, поскольку существует только 26 различных букв, занимает место O (1 )). Как только вы найдете все 26 букв, у вас будет длина кратчайшего панграмматического окна, начинающегося в данной точке. Каждое сканирование может занимать время O (n ), а количество сканирований составляет O (n ), что в сумме составляет O (n ²)времени.

Мы также можем решить эту задачу за время O (n log n )и в пространстве O (n ), используя модифицированный бинарный поиск. Создайте 26 массивов, по одному для каждой буквы алфавита, затем заполните эти массивы позициями каждой буквы во входном тексте в отсортированном порядке. Мы можем сделать это, просто просматривая текст, добавляя каждый индекс к массиву, соответствующему текущему символу. Получив это, мы можем найти за время O (log n )длину кратчайшего панграмматического окна, начинающегося с некоторого индекса, выполнив 26 двоичных поисков в массивах, чтобы найти самое раннее время появления каждого символа в массиве. входной массив в или после данного индекса. Какое из этих чисел наибольшее, дает символ «длинного полюса», который появляется дальше всего в строке и, таким образом, дает конечную точку панграмматического окна. Выполнение этого шага поиска занимает O (log n )времени, и, поскольку мы должны сделать это для всех n символов в строке, общее время выполнения составляет O (n log n ), с O (. ] n )использование памяти для массивов.

Дальнейшим усовершенствованием описанного выше подхода является замена массивов и бинарного поиска деревьями ван Эмде-Боаса и предшествующими поисками. Это увеличивает время создания до O (n log log n ), но сокращает время каждого поиска до O (log log n )времени для чистого времени выполнения O (n log log n )с использованием O (n )пространства.

Существуют ли лучшие алгоритмы?