Лексикографически K-наименьшая строка, содержащая «a» X раз и «b» Y раз

Учитывая три неотрицательных целых числа, X , Y , и K , Задача состоит в том, чтобы найти K-ю наименьшую лексикографическую строку, содержащую X вхождений символа «a» и Y вхождений символа «b» .

Примеры:

Input: X = 2, Y = 3, K = 3
Output: abbab
Explanation: 
First lexicographical smallest string = “aabbb”.
Second lexicographical smallest string = “ababb”.
Third lexicographical smallest string = “abbab”.

Input: X = 4, Y = 3, K = 4
Output: aaabbba

Наивный подход: самый простой подход состоит в том, чтобы сгенерировать все различные перестановки строки X вхождений символа 'a' и Y вхождений символа 'b' . Затем сначала отсортируйте массив выходных строк в лексикографическом порядке и напечатайте строку индекса K.

Временная сложность: O(N*N!), где N равно (X + Y)
Вспомогательное пространство: O(N!)

Эффективный подход: эта проблема имеет свойство перекрывающихся подзадач и свойство оптимальной подструктуры. Так что эту проблему можно решить с помощью динамического программирования. Как и в других типичных задачах динамического программирования (DP), повторного вычисления одних и тех же подзадач можно избежать, создав временный массив, в котором хранятся результаты подзадач. Выполните следующие действия, чтобы решить эту проблему.

• Инициализируйте двумерный массив, dp[][] где dp[i][j] обозначает количество строк, содержащих i количество a и j количество b .
• Итерация в диапазоне [0, X] с использованием переменной i :
  • Выполните итерацию в диапазоне [0, Y], используя переменную j:
    • Если i больше 0, то обновите dp[i][j] до dp[i][j] + dp[i-1][j] .
    • Если j больше 0 , то обновите dp[i][j] до dp[i][j] + dp[i][j-1] .
• Теперь рекурсивно найдите K-ю лексикографическую наименьшую строку, вызвав функцию kthString (int X, int Y, int K) .
• Обработка базовых случаев:
  • Если присутствуют только символы «a», верните строку из всех символов «a» .
  • Если присутствуют только символы «b», верните строку из всех символов «b» .
• Если имеется более или равно K строк, начинающихся с «a» , то вернуть «a» + kthString(X-1, Y, K) .
• В противном случае первым символом результирующей строки будет «b» , верните «b» + kthString(X, Y-1, K – dp[X-1][Y]) .

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

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

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

• Объявите двумерный массив dp , где dp[i][j] обозначает количество строк, содержащих i число a и j число b .
• Итерация в диапазоне [0, X] с использованием переменной i :
  • Выполните итерацию в диапазоне [0, Y], используя переменную j:
    • Если i больше 0, то обновите dp[i][j] до dp[i][j] + dp[i-1][j].
    • Если j больше 0 , то обновите dp[i][j] до dp[i][j] + dp[i][j-1].
• Теперь итеративно найдите K-ю лексикографически наименьшую строку.
• Перемещайтесь, пока X больше 0 , а Y больше 0 :
  • Если имеется более или равно K строк, начинающихся с 'a' , то напечатайте 'a' и уменьшите X на 1 .
  • В противном случае первым символом результирующей строки будет 'b' , напечатайте 'b' и уменьшите Y на 1 .
• Если присутствуют только символы ' a', выведите строку из всех символов ' a '.
• Если присутствуют только символы ' b ', выведите строку из всех символов ' b '.

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

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