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++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find sequence// from given string // according to given rulevoid 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 Codeint main(){ int N = 5; string S = "FBBFB"; // Printing the sequence findSequence(N, S); return 0;} |
Java
// JAVA program for above approachimport 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 |
Python3
# Python program for above approachfrom collections import deque# Function to find sequence# from given string# according to given ruledef 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 CodeN = 5S = "FBBFB"# Printing the sequencefindSequence(N, S)# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for above approachusing 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 |
Javascript
<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> |
Output
1 2 4 5 3 0
Time Complexity: O(N)
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!
