Find Array formado al invertir el prefijo cada vez que se encuentra el carácter dado

Dada una array arr[] de longitud N que consta solo de letras mayúsculas en inglés y una letra ch . la tarea es encontrar la array final que se formará invirtiendo el prefijo cada vez que se encuentre la letra ch en la array.

Ejemplos :

Entrada : arr[] = {‘A’, ‘B’, ‘X’, ‘C’, ‘D’, ‘X’, ‘F’}, ch= ‘X’
Salida : DCXABXF 
Explicación : 
Primer encuentro de ‘ X’ en el índice 2, Subconjunto inicial = A, B, Subconjunto final = B, A, X.
Segundo encuentro de ‘X’ en el índice 5, Subconjunto inicial = B, A, X, C, D 
Subconjunto final = D, C , X, A, B, X (agregado).
Subconjunto final después de atravesar, = D, C, X, A, B, X, F

Entrada : arr[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}, ch = ‘F’
Salida : ABCDE

Planteamiento : La idea para resolver el problema es la siguiente:

Si cada porción entre dos ocurrencias de ch (o los extremos de la array) se considera un segmento, entonces las inversiones de prefijo de la string se pueden visualizar como agregando los caracteres de un segmento alternativamente al principio y al final de la string y seguir expandiéndose. hacia fuera. 

• Entonces, la idea es empujar el elemento de la array al final de una lista hasta que ch ocurra por primera vez. 
• Cuando ocurra el primer ch , empuje los elementos, incluido ch , al frente de la lista hasta que ocurra el siguiente ch . Nuevamente, si ocurre ch , empuje los elementos al final de la lista, incluido ch . 
• Entonces, la conclusión es que cada vez que ocurre ch , tienes que cambiar la dirección de empuje de los elementos.

Nota : si hay un número impar de K en la array, debe invertir la lista a medida que comenzamos a empujar el elemento desde atrás.

Siga los pasos que se detallan a continuación

•  Crea una lista llamada li para almacenar los elementos .
•  Cree una variable llamada encontrada para verificar de qué lado tiene que agregar los elementos
•  Si ocurre ch , cambie el valor de encontrado de 1 a 0 o de 0 a 1.
  • Si encontrado es igual a 1 , agregue los elementos al frente . 
  • De lo contrario, agregue los elementos en la parte posterior.
•  Si ch ocurre un número impar de veces, invierta la lista e imprima, de lo contrario imprímala simplemente 

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

// C++ code to implement the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Final string after performing all the
// operations
  
list<char> findFinalString(char* arr, int n, char ch)
{
    list<char> li;
    bool found = 0;
  
    for (int i = 0; i < n; i++) {
  
        // ch Found
        if (arr[i] == ch)
            found = !found;
  
        // Push character at front of list
        if (found)
            li.push_front(arr[i]);
  
        // Push character at back of list
        else
            li.push_back(arr[i]);
    }
  
    // If there is odd number of ch
    if (found == 1)
        li.reverse();
  
    // Return the list
    return li;
}
  
// Driver Code
int main()
{
    char arr[] = { 'A', 'B', 'X', 'C', 'D', 'X', 'F' };
    char ch = 'X';
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    list<char> ans = findFinalString(arr, N, ch);
    for (auto itr = ans.begin();
         itr != ans.end(); itr++)
        cout << *itr << " ";
  
    return 0;
}

D C X A B X F 

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