Genere una secuencia insertando posiciones en Array en función del valor de string correspondiente

Dada una string S de longitud N . La string consta únicamente de las letras ‘F’ y ‘B’ . La tarea es generar una secuencia realizando algunas operaciones tales que:

• Considere una secuencia entera A que consta de sólo un 0, es decir, A = (0).
• Ahora, para cada índice (i) de la string (1 a N), si S[i] es ‘F’, agregue i al frente inmediato (es decir, lado izquierdo) de i-1 en la secuencia A
• De lo contrario, si S[i] es ‘B’, agregue i a la parte posterior inmediata (es decir, al lado derecho) de i-1 secuencia A .
• Imprime la secuencia resultante A .

Ejemplos :

Entrada : N = 5, S = “FBBFB”
Salida : 1 2 4 5 3 0
Explicación : Inicialmente, A = {0}.
S[1] es ‘F’, la secuencia se convierte en { 1 , 0}
S[2] es ‘B’, la secuencia se convierte en {1, 2 , 0}
S[3] es ‘B’, la secuencia se convierte en {1, 2, 3 , 0}
S[4] es ‘F’, la secuencia se convierte en {1, 2, 4 , 3, 0}
S[5] es ‘B’, la secuencia se convierte en {1, 2, 4, 5 , 3, 0}

Entrada : N = 6, S = “BBBBBB”
Salida : 0 1 2 3 4 5 6

Planteamiento: La idea para resolver el problema se basa en el concepto de dequeue. 

Como en cada iteración, es posible que la inserción de i pueda ocurrir desde cualquier extremo de ( i-1) , por lo tanto , se puede usar  deque ya que en dequeue la inserción es posible desde cualquier extremo.

Siga los pasos para la solución:

• La observación en el enfoque es que el problema se vuelve más simple después de invertir todas las operaciones.
• El problema ahora se modifica a una secuencia dada que consta solo de (N), y después de cada iteración desde el final de la string,
  • Si S[i] es ‘F’, empuje i a la derecha de i-1 ,
  • Si S[i] es ‘B’, empuje i a la izquierda de i-1 en el dequeue .
• Devuelve los elementos de dequeue en el orden desde el frente.

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

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find sequence
// from given string
// according to given rule
void findSequence(int N, string S)
{
 
    // Creating a deque
    deque<int> v;
 
    // Inserting N (size of string) into deque
    v.push_back(N);
 
    // Iterating string from behind and
    // pushing the indices into the deque
    for (int i = N - 1; i >= 0; i--) {
 
        // If letter at current index is 'F',
        // push i to the right of i-1
        if (S[i] == 'F') {
            v.push_back(i);
        }
 
        // If letter at current index is 'B',
        // push i to the left of i-1
        else {
            v.push_front(i);
        }
    }
 
    // Printing resultant sequence
    for (int i = 0; i <= N; i++)
        cout << v[i] << " ";
}
 
// Driver Code
int main()
{
    int N = 5;
    string S = "FBBFB";
 
    // Printing the sequence
    findSequence(N, S);
    return 0;
}

// JAVA program for above approach
import java.util.*;
class GFG
{
 
  // Function to find sequence
  // from given string
  // according to given rule
  public static void findSequence(int N, String S)
  {
 
    // Creating a deque
    Deque<Integer> v = new ArrayDeque<Integer>();
 
    // Inserting N (size of string) into deque
    v.addLast(N);
 
    // Iterating string from behind and
    // pushing the indices into the deque
    for (int i = N - 1; i >= 0; i--) {
 
      // If letter at current index is 'F',
      // push i to the right of i-1
      if (S.charAt(i) == 'F') {
        v.addLast(i);
      }
 
      // If letter at current index is 'B',
      // push i to the left of i-1
      else {
        v.addFirst(i);
      }
    }
 
    // Printing resultant sequence
    for (Iterator itr = v.iterator(); itr.hasNext();) {
      System.out.print(itr.next() + " ");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 5;
    String S = "FBBFB";
 
    // Printing the sequence
    findSequence(N, S);
  }
}
 
// This code is contributed by Taranpreet

# Python program for above approach
from collections import deque
 
# Function to find sequence
# from given string
# according to given rule
def findSequence(N, S):
 
    # Creating a deque
    v = deque()
 
    # Inserting N (size of string) into deque
    v.append(N)
 
    # Iterating string from behind and
    # pushing the indices into the deque
    i = N - 1
    while(i >= 0):
 
        # If letter at current index is 'F',
        # push i to the right of i-1
        if (S[i] == 'F'):
            v.append(i)
 
        # If letter at current index is 'B',
        # push i to the left of i-1
        else:
            v.appendleft(i)
 
        i -= 1
 
    # Printing resultant sequence
    print(*v)
 
# Driver Code
N = 5
S = "FBBFB"
 
# Printing the sequence
findSequence(N, S)
 
# This code is contributed by Samim Hossain Mondal.

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to find sequence
  // from given string
  // according to given rule
  public static void findSequence(int N, String S)
  {
 
    // Creating a deque
    List<int> v = new List<int>();
 
    // Inserting N (size of string) into deque
    v.Add(N);
 
    // Iterating string from behind and
    // pushing the indices into the deque
    for (int i = N - 1; i >= 0; i--) {
 
      // If letter at current index is 'F',
      // push i to the right of i-1
      if (S[i] == 'F') {
        v.Add(i);
      }
 
      // If letter at current index is 'B',
      // push i to the left of i-1
      else {
        v.Insert(0,i);
      }
    }
 
    // Printing resultant sequence
    foreach (int itr in v) {
      Console.Write(itr + " ");
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int N = 5;
    String S = "FBBFB";
 
    // Printing the sequence
    findSequence(N, S);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
    // JavaScript program for above approach
 
 
    // Function to find sequence
    // from given string
    // according to given rule
    const findSequence = (N, S) => {
 
        // Creating a deque
        let v = [];
 
        // Inserting N (size of string) into deque
        v.push(N);
 
        // Iterating string from behind and
        // pushing the indices into the deque
        for (let i = N - 1; i >= 0; i--) {
 
            // If letter at current index is 'F',
            // push i to the right of i-1
            if (S[i] == 'F') {
                v.push(i);
            }
 
            // If letter at current index is 'B',
            // push i to the left of i-1
            else {
                v.unshift(i);
            }
        }
 
        // Printing resultant sequence
        for (let i = 0; i <= N; i++)
            document.write(`${v[i]} `);
    }
 
    // Driver Code
 
    let N = 5;
    let S = "FBBFB";
 
    // Printing the sequence
    findSequence(N, S);
 
// This code is contributed by rakeshsahni
 
</script>

1 2 4 5 3 0 

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