Lexicographically smallest permutation of [ 1 , N ] based on given Binary string | C ++ program for the above approach ; Function to generate the lexicographically smallest permutation according to the given criteria ; Stores the resultant permutation ; Initialize the first elements to 1 ; Traverse the given string S ; Number greater than last number ; Number equal to the last number ; Correct all numbers to the left of the current index ; Printing the permutation ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void constructPermutation ( string S , int N ) { int ans [ N ] ; ans [ 0 ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) { if ( S [ i - 1 ] == '0' ) { ans [ i ] = i + 1 ; } else { ans [ i ] = ans [ i - 1 ] ; } for ( int j = 0 ; j < i ; ++ j ) { if ( ans [ j ] >= ans [ i ] ) { ans [ j ] ++ ; } } } for ( int i = 0 ; i < N ; i ++ ) { cout << ans [ i ] ; if ( i != N - 1 ) { cout << " ▁ " ; } } } int main ( ) { string S = "100101" ; constructPermutation ( S , S . length ( ) + 1 ) ; return 0 ; }