Estado final de la string después de la modificación.

Dada una string S de longitud n que representa n cajas adyacentes entre sí. 

1. Un carácter R en el índice i representa que el cuadro i-ésimo está siendo empujado hacia la derecha.
2. Por otro lado, L en el índice i representa que la i-ésima casilla está siendo empujada hacia la izquierda.
3. y un . representa un espacio vacío.

Comenzamos con la configuración inicial, en cada unidad de tiempo, una caja que se empuja hacia la derecha empuja la siguiente caja hacia la derecha y lo mismo ocurre con una caja que se empuja hacia la izquierda. La tarea es imprimir las posiciones finales de todas las casillas cuando no sea posible realizar más movimientos. Si hay una substring «RL», entonces el cuadro central se empuja desde ambas direcciones y, por lo tanto, ya no se mueve.

Ejemplos:  

Entrada: S = “RR.L” 
Salida: RR.L 
Los cuadros primero y segundo están hacia la derecha. El punto central está siendo empujado desde ambas direcciones, por lo que no se mueve.

Entrada: S = “R..R…L.” 
Salida: RRRRR.LL. 
En la unidad de tiempo 1: 
El primer cuadro empuja al segundo cuadro. 
La tercera caja empuja la cuarta caja. 
El penúltimo cuadro empuja al penúltimo cuadro, la configuración se convierte en 
«RR.RR.LL». 
En la unidad de tiempo 2: 
el segundo cuadro empuja al tercer cuadro, la string se convierte en 
«RRRRR.LL». 

Enfoque: podemos calcular la fuerza neta aplicada en cada caja. Las fuerzas que nos importan son qué tan cerca está una caja de una R hacia la izquierda o de una L hacia la derecha, es decir, cuanto más cerca estemos, más fuerte será la fuerza. 

• Al escanear de izquierda a derecha, la fuerza decae en 1 en cada iteración y se restablece a N si encontramos una R nuevamente.
• De manera similar, de derecha a izquierda, podemos encontrar las fuerzas desde la derecha (cercanía a L ).
• Para algún resultado de caja[i], si las fuerzas son iguales, entonces el resultado es . ya que ambos lados le aplican la misma fuerza. De lo contrario, nuestro resultado está implícito en la fuerza más fuerte.

Para la string S = “R..R…L.”  
Las fuerzas que van de izquierda a derecha son [7, 6, 5, 7, 6, 5, 4, 0, 0] . 
Las fuerzas que van de derecha a izquierda son [0, 0, 0, 0, -4, -5, -6, -7, 0] . 
Combinándolos (tomando su suma aritmética en cada índice) da resultado = [7, 6, 5, 7, 2, 0, -2, -7, 0] . 
Por lo tanto, la respuesta final es RRRRR.LL. 
 

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return final
// positions of the boxes
string pushBoxes(string S)
{
    int N = S.length();
    vector<int> force(N, 0);
 
    // Populate forces going
    // from left to right
    int f = 0;
    for(int i = 0; i < N; i++)
    {
        if (S[i] == 'R')
        {
            f = N;
        }
        else if (S[i] == 'L')
        {
            f = 0;
        }
        else
        {
            f = max(f - 1, 0);
        }
        force[i] += f;
    }
 
    // Populate forces going from right to left
    f = 0;
    for(int i = N - 1; i >= 0; i--)
    {
        if (S[i] == 'L')
        {
            f = N;
        }
        else if (S[i] == 'R')
        {
            f = 0;
        }
        else
        {
            f = max(f - 1, 0);
        }
        force[i] -= f;
    }
 
    // return final state of boxes
    string ans;
    for(int f : force)
    {
        ans += f == 0 ? '.' : f > 0 ? 'R' : 'L';
    }
    return ans;
}
 
// Driver code
int main()
{
    string S = ".L.R...LR..L..";
     
    // Function call to print answer
    cout << pushBoxes(S);
}
 
// This code is contributed by sanjeev2552

# Python3 implementation of above approach
 
# Function to return final
# positions of the boxes
def pushBoxes(S):
 
    N = len(S)
    force = [0] * N
 
    # Populate forces going from left to right
    f = 0
    for i in range(0, N):
 
        if S[i] == 'R':
            f = N
        elif S[i] == 'L':
            f = 0
        else:
            f = max(f - 1, 0)
        force[i] += f
 
    # Populate forces going from right to left
    f = 0
    for i in range(N - 1, -1, -1):
 
        if S[i] == 'L':
            f = N
        elif S[i] == 'R':
            f = 0
        else:
            f = max(f - 1, 0)
        force[i] -= f
 
    # return final state of boxes
    return "".join('.' if f == 0 else 'R' if f > 0 else 'L'
                   for f in force)
 
 
# Driver code
S = ".L.R...LR..L.."
 
# Function call to print answer
print(pushBoxes(S))

LL.RR.LLRRLL..

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)