Когда в задаче требуется найти множество лексикографически минимальных строк, имеет смысл воспользоваться бором. Разумеется, просто построить бор на всех возможных звучаниях слов не особо реалистично, так как нас интересуют k минимальных, а всего их порядка 2n, что сильно больше.
Однако можно использовать несколько оптимизаций, чтобы строить k лексикографически минимальных строк быстрее. Для этого необходимо понимать, как строится лексикографически минимальная строка, а также как по любой строке построить следующую в лексикографическом порядке.
Построить минимальную строку не сложно: достаточно заметить, что она состоит из одного единственного минимального звука. Соответственно, эта задача просто эквивалентна поиску минимума в массиве a.
Поиск лексикографически следующей строки устроен следующим образом:
Итого: в качестве минимальной строки выберем самое левое вхождение минимального звука в a. Далее k раз сделаем следующее:
Для эффективного выполнения этих операций достаточно иметь дерево отрезков на операцию «минимум» на алфавите (или просто суффиксные минимумы), а также хранить текущую строку в декартовом дереве по неявному ключу (в вершине храним флаг «есть ли в поддерева буква, которую можно увеличить», а также хеш поддерева). Хеши пересчитываются автоматически, а все описанные операции сводятся к операциям split и merge для ДД по неявному ключу — общее время работы .