Generar una secuencia determinada por los caracteres de una string dada

Dada una string binaria S de longitud N ( 1 ≤ N ≤ 10 ⁵ ), la tarea es imprimir una permutación A que consta de números enteros de 0 a N que cumplan las siguientes condiciones:

• Si S[i] = 1 , entonces A[i] < A[i + 1] .
• Si S[i] = 0 , entonces A[i] > A[i + 1] .

Ejemplos: 
 

Entrada: S = “001”  
Salida: [3, 2, 0, 1]  
Explicación: 
S[0] = 0 y A[0] (= 3) > A[1] (= 2) 
S[1] = 0 y A[1] (= 2) > A[2] (= 0) 
S[2] = 1 y A[2] (= 0) > A[3] (= 1) 
 

Entrada: S = “1010”  
Salida: [0, 4, 1, 3, 2]

Enfoque: siga los pasos a continuación para resolver el problema:

• Asigne el número más bajo posible si el carácter encontrado en la string es ‘1’ .
• Asigne el número más alto posible si el carácter encontrado en la string es ‘0’ .
• Establezca dos punteros lo (= 0) , almacenando el nivel más bajo posible actual, y hi (= N) , almacenando el nivel más alto posible actual.
• Recorra la string y agregue los valores a la array resultante, digamos re s, desde el rango usando los dos punteros en consecuencia.
• Después de completar el recorrido de la string, solo queda un valor para agregar. Agregue lo al último índice.
• Imprima la array res como el resultado requerido.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the
// required sequence
void StringPattern(string S)
{
    // Length of the string
    int n = (int)S.size();
 
    // Pointers to store lowest and
    // highest possible values
    int l = 0, r = n;
 
    // Stores the required answer
    vector<int> res(n + 1, 0);
 
    for (int i = 0; i < n; i++) {
 
        switch (S[i]) {
 
        // If current character is '1'
        case '1':
 
            // Assign smallest
            // possible value
            res[i] = l++;
            break;
 
        // If current character is '0'
        case '0':
 
            // Assign largest
            // possible value
            res[i] = r--;
            break;
        }
    }
 
    // At this point, l == r ，
    // only one value is not assigned yet.
    res[n] = l;
    for (int el : res) {
        cout << el << " ";
    }
}
 
// Driver Code
int main()
{
    string s = "001";
    StringPattern(s);
 
    return 0;
}

// Java Implementation of above approach
import java.util.*;
class GFG
{
 
// function to find minimum required permutation
static void StringPattern(String s)
{
    int n = s.length();
    int l = 0, r = n; 
    int [] res = new int[n + 1];
    for (int x = 0; x < n; x++)
    {
        if (s.charAt(x) == '1')
        {
            res[x] = l++;
        }
        else if(s.charAt(x) == '0')
        {
            res[x] = r--;
        }
    }    
    res[n] = l;
    for(int i = 0; i < n+1; i++)
    {
        System.out.print(res[i]+" ");
    }
}
 
// Driver code
public static void main(String[] args)
{
    String s = "001";
    StringPattern(s);
}
}
 
// This code is contributed by mohit kumar 29.

# Python program to implement
# the above approach
 
# Function to print the
# required sequence
def StringPattern(S):
 
    # Stores the lowest, highest
    # possible values that can be
    # appended, size of the string
    lo, hi = 0, len(S)
 
    # Stores the required result
    ans = []
 
    # Traverse the string
    for x in S:
 
        # If current character is '1'
        if x == '1':
 
            # Append lowest
            # possible value
            ans.append(lo)
 
            lo += 1
 
        # If current character is '0'
        else:
 
            # Append highest
            # possible value
            ans.append(hi)
 
            hi -= 1
 
    return ans + [lo]
 
 
# Driver Code
if __name__ == "__main__":
        # Input
    s = '001'
    print(StringPattern(s))

// C# Implementation of above approach
using System;
class GFG
{
 
// function to find minimum required permutation
static void StringPattern(String s)
{
    int n = s.Length;
    int l = 0, r = n; 
    int [] res = new int[n + 1];
    for (int x = 0; x < n; x++)
    {
        if (s[x] == '1')
        {
            res[x] = l++;
        }
        else if(s[x] == '0')
        {
            res[x] = r--;
        }
    }    
    res[n] = l;
    for(int i = 0; i < n + 1; i++)
    {
        Console.Write(res[i] + " ");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "001";
    StringPattern(s);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program of
// the above approach
 
 // function to find minimum
 // required permutation
function StringPattern(s)
{
    let n = s.length;
    let l = 0, r = n;
    let res = new Array(n+1).fill(0);
    for (let x = 0; x < n; x++)
    {
        if (s[x] == '1')
        {
            res[x] = l++;
        }
        else if(s[x] == '0')
        {
            res[x] = r--;
        }
    }   
    res[n] = l;
    for(let i = 0; i < n+1; i++)
    {
        document.write(res[i]+" ");
    }
}
 
    // Driver Code
     
    let s = "001";
    StringPattern(s);
  
</script>

3 2 0 1

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)