Лексикографически наименьшая строка максимальной длины, состоящая из первых K алфавитов, не содержащая повторяющихся подстрок.

Для заданного положительного целого числа K задача состоит в том, чтобы найти лексикографически наименьшую строку, которая может быть сгенерирована с использованием первых K строчных алфавитов, так что ни одна подстрока длины не менее 2 не повторяется в сгенерированной строке.

Примеры:

Input: K = 3
Output: aabacbbcca
Explanation:
In the string “aabacbbcca”, all possible substrings of length at least 2 is repeated more than once.

Input: K = 4
Output: aabacadbbcbdccdda

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Если все подстроки длины 2 уникальны, то все подстроки длины больше 2 также будут уникальны.
• Следовательно, строка максимальной длины должна содержать все уникальные подстроки длины 2, расположенные в лексикографическом порядке так, чтобы никакие 3 последовательных символа в строке не были одинаковыми.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте строку, скажем, S как пустую строку, в которой хранится результирующая строка.
• Переберите все первые K символов строчного алфавита, используя переменную, скажем, i , и выполните следующие шаги:
  • Добавьте текущий символ i к строке S .
  • Перейдите от (i + 1) ^-го символа к K ^-му символу и добавьте символ i , за которым следует символ j , к строке S.
  • Добавьте к строке S символ 'a' , чтобы подстрока, состоящая из последнего и первого алфавита, также присутствовала в результирующей строке.
• После выполнения вышеуказанных шагов выведите строку S в качестве результирующей строки.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(K ² )
Вспомогательное пространство: O(K ² )