Generate a Sequence by inserting positions into Array based on corresponding String value

Given a string S of length N. The string consists only of letters 'F' and 'B'. The task is to generate a sequence performing some operations such that:

• Consider an integer sequence A that consists of only a 0, i.e. A = (0).
• Now, for each index(i) of the string (1 to N), if S[i] is 'F' add i to the immediate front (i.e. left side) of i-1 in sequence A
• Else if S[i] is 'B' add i to the immediate back (i.e. right side) of i-1 sequence A.
• Print the resultant sequence A.

Examples :

Input: N = 5, S = "FBBFB"
Output: 1 2 4 5 3 0
Explanation: Initially, A = {0}.
S[1] is 'F' , sequence becomes {1, 0}
S[2] is 'B' , sequence becomes {1, 2, 0}
S[3] is 'B' , sequence becomes {1, 2, 3, 0}
S[4] is 'F' , sequence becomes {1, 2, 4, 3, 0}
S[5] is 'B' , sequence becomes {1, 2, 4, 5, 3, 0}

Input : N = 6 , S = "BBBBBB"
Output : 0 1 2 3 4 5 6

Approach: The idea to solve the problem is based on the concept dequeue. 

As at each iteration, it is possible that insertion of i may occur from any end of (i-1), therefore deque can be used as in dequeue insertion is possible from any end. 

Follow the steps for the solution:

• The observation in the approach is that the problem becomes more simple after inverting all the operations.
• The problem now modifies to, a given sequence that consists of only (N), and after each iteration from the end of the string,
  • If S[i] is 'F', push i to the right of i-1,
  • If S[i] is 'B', push i to the left of i-1 in the dequeue.
• Return the elements of dequeue in the order from the front end.

Below is the implementation of the above approach.

// 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 

Time Complexity: O(N)
Auxiliary Space: O(N)