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

Опубликовано: 19 Сентября, 2022

Даны два целых числа N и K , задача состоит в том, чтобы сформировать строку размера N , используя первые K символов алфавита, соблюдая заданные условия:

  • Никакие два соседних символа строки не совпадают.
  • Все K символов присутствуют в строке хотя бы один раз.

Если такая строка невозможна, выведите -1.

Примеры:

Input: N = 3, K = 2
Output: “aba”
Explanation: This is the lexicographically smallest string which follows the condition.
“aaa” is lexicographically smallest string of size 3, but this does not contain ‘b’.
So it is not a valid string according to the statement.
“aab” is also lexicographically smaller, but it violates the condition of two adjacent characters not being the same.

Input: N = 2, K = 3
Output: -1
Explanation: Have to choose first 3 characters, but a string of only 2 size should be formed.
So it is not possible to use all of the first 3 characters.

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

  • если N < K или K = 1 и N > 1 , то выведите '-1', так как формирование строки, удовлетворяющей обоим условиям, невозможно.
  • В противном случае, если N = 2 , выведите «ab» .
  • Если N > 2 , то поочередно добавляйте в результирующую строку 'a' и 'b' , пока оставшаяся длина не будет равна K-2 . Затем добавьте оставшиеся символы, кроме «а» и «б», в лексикографическом порядке.
  • Последняя строка является обязательной строкой.

Ниже приведена реализация описанного выше подхода.


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

РЕКОМЕНДУЕМЫЕ СТАТЬИ