Given a binary string S of size (N – 1), the task is to find the lexicographically smallest permutation P of the first N natural numbers such that for every index i, if S[i] equals ‘0‘ then P[i + 1] must be greater than P[i] and if S[i] equals ‘1‘ then P[i + 1] must be less than P[i].
Examples:
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 < 7Input: N = 4, S = 000
Output: 1 2 3 4
Approach: The given problem can be solved by using the Greedy Approach by using smaller numbers at lower indices as much as possible will create the lexicographically smallest permutations. Follow the steps below to solve the problem:
- Initialize an array, say ans[] of size N that stores the resultant permutation.
- Traverse the given string S and perform the following steps:
- If the value of S[i] equals ‘0‘ then assign the number greater than the last assigned number.
- Otherwise, assign the smallest number which is larger than all currently used numbers.
- After completing the above steps, print the resultant permutation formed in the array ans[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to generate the lexicographically// smallest permutation according to the// given criteriavoid constructPermutation(string S, int N){ // Stores the resultant permutation int ans[N]; // Initialize the first elements to 1 ans[0] = 1; // Traverse the given string S for (int i = 1; i < N; ++i) { if (S[i - 1] == '0') { // Number greater than last // number ans[i] = i + 1; } else { // Number equal to the last // number ans[i] = ans[i - 1]; } // Correct all numbers to the left // of the current index for (int j = 0; j < i; ++j) { if (ans[j] >= ans[i]) { ans[j]++; } } } // Printing the permutation for (int i = 0; i < N; i++) { cout << ans[i]; if (i != N - 1) { cout << " "; } }}// Driver Codeint main(){ string S = "100101"; constructPermutation(S, S.length() + 1); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to generate the lexicographically // smallest permutation according to the // given criteria static void constructPermutation(String S, int N) { // Stores the resultant permutation int[] ans = new int[N]; // Initialize the first elements to 1 ans[0] = 1; // Traverse the given string S for (int i = 1; i < N; ++i) { if (S.charAt(i - 1) == '0') { // Number greater than last // number ans[i] = i + 1; } else { // Number equal to the last // number ans[i] = ans[i - 1]; } // Correct all numbers to the left // of the current index for (int j = 0; j < i; ++j) { if (ans[j] >= ans[i]) { ans[j]++; } } } // Printing the permutation for (int i = 0; i < N; i++) { System.out.print(ans[i]); if (i != N - 1) { System.out.print(" "); } } } // Driver Code public static void main(String[] args) { String S = "100101"; constructPermutation(S, S.length() + 1); }}// This code is contributed by code_hunt. |
Python3
# Python Program to implement# the above approach# Function to generate the lexicographically# smallest permutation according to the# given criteriadef constructPermutation(S, N): # Stores the resultant permutation ans = [0] * N # Initialize the first elements to 1 ans[0] = 1 # Traverse the given string S for i in range(1, N): if (S[i - 1] == '0'): # Number greater than last # number ans[i] = i + 1 else : # Number equal to the last # number ans[i] = ans[i - 1] # Correct all numbers to the left # of the current index for j in range(i): if (ans[j] >= ans[i]): ans[j] += 1 # Printing the permutation for i in range(N): print(ans[i], end="") if (i != N - 1): print(" ", end="") # Driver CodeS = "100101"constructPermutation(S, len(S) + 1)# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG { // Function to generate the lexicographically // smallest permutation according to the // given criteria static void constructPermutation(string S, int N) { // Stores the resultant permutation int[] ans = new int[N]; // Initialize the first elements to 1 ans[0] = 1; // Traverse the given string S for (int i = 1; i < N; ++i) { if (S[i - 1] == '0') { // Number greater than last // number ans[i] = i + 1; } else { // Number equal to the last // number ans[i] = ans[i - 1]; } // Correct all numbers to the left // of the current index for (int j = 0; j < i; ++j) { if (ans[j] >= ans[i]) { ans[j]++; } } } // Printing the permutation for (int i = 0; i < N; i++) { Console.Write(ans[i]); if (i != N - 1) { Console.Write(" "); } } } // Driver Code public static void Main() { string S = "100101"; constructPermutation(S, S.Length + 1); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to generate the lexicographically // smallest permutation according to the // given criteria function constructPermutation(S, N) { // Stores the resultant permutation let ans = new Array(N); // Initialize the first elements to 1 ans[0] = 1; // Traverse the given string S for (let i = 1; i < N; ++i) { if (S[i - 1] == '0') { // Number greater than last // number ans[i] = i + 1; } else { // Number equal to the last // number ans[i] = ans[i - 1]; } // Correct all numbers to the left // of the current index for (let j = 0; j < i; ++j) { if (ans[j] >= ans[i]) { ans[j]++; } } } // Printing the permutation for (let i = 0; i < N; i++) { document.write(ans[i]); if (i != N - 1) { document.write(" "); } } } // Driver Code let S = "100101"; constructPermutation(S, S.length + 1);// This code is contributed by Potta Lokesh </script> |
Output:
2 1 3 5 4 7 6
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
