Лексикографически наименьшая перестановка [1, N] на основе заданной двоичной строки

Для заданной двоичной строки S размера (N – 1) задача состоит в том, чтобы найти лексикографически наименьшую перестановку P первых N натуральных чисел, такую, что для каждого индекса i , если S[i] равно ' 0 ', то P[i + 1 ] должно быть больше P[i] и если S[i] равно ' 1 ', то P[i + 1] должно быть меньше P[i] .

Примеры:

Input: N = 7, S = 100101
Output: 2 1 3 5 4 7 6
Explanation:
Consider the permutation as {2, 1, 3, 5, 4, 7, 6} that satisfy the given criteria as:
For index 0, S[0] = 1, P[1] < P[0], i.e. 1 < 2
For index 1, S[1] = 0, P[2] < P[1], i.e. 3 > 1
For index 2, S[2] = 0, P[3] < P[2], i.e. 5 > 3
For index 3, S[3] = 1, P[4] < P[3], i.e. 4 < 5
For index 4, S[4] = 0, P[5] < P[4], i.e. 7 > 4
For index 5, S[5] = 1, P[6] < P[5], i.e. 6 < 7

Input: N = 4, S = 000
Output: 1 2 3 4

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

• Инициализируйте массив, скажем, ans[] размера N , в котором хранится результирующая перестановка.
• Пройдите по заданной строке S и выполните следующие шаги:
  • Если значение S[i] равно ' 0 ', тогда присвойте номер больше, чем последний назначенный номер.
  • В противном случае назначьте наименьшее число, которое больше, чем все используемые в настоящее время числа.
• После выполнения вышеуказанных шагов выведите результирующую перестановку, сформированную в массиве ans[] .

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

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