Programa C++ para modificar una string realizando operaciones de cambio dadas

Dada una string S que contiene alfabetos ingleses en minúsculas y una array shift[][] que consta de pares de la forma {direction, cantidad} , donde la dirección puede ser 0 (para desplazamiento a la izquierda) o 1 (para desplazamiento a la derecha) y la cantidad es el número de índices por los que se requiere desplazar la string S. La tarea es devolver la string modificada que se puede obtener después de realizar las operaciones dadas.
Nota: Un desplazamiento a la izquierda de 1 se refiere a eliminar el primer carácter de S y agregarlo al final. De manera similar, un desplazamiento a la derecha de 1 se refiere a eliminar el último carácter de Se insertar al principio.

Ejemplos

Entrada : S = “abc”, shift[][] = {{0, 1}, {1, 2}}
Salida: cab
Explicación: 
[0, 1] se refiere a desplazar S[0] a la izquierda en 1. Por lo tanto, la string S se modifica de “abc” a “bca”.
[1, 2] se refiere a desplazar S[0] a la derecha en 1. Por lo tanto, la string S se modifica de «bca» a «cab».

Entrada: S = “abcdefg”, shift[][] = { {1, 1}, {1, 1}, {0, 2}, {1, 3} }
Salida: efgabcd
Explicación:  
[1, 1] se refiere a desplazar S[0] a la derecha en 1. Por lo tanto, la string S se modifica de «abcdefg» a «gabcdef».
[1, 1] se refiere a desplazar S[0] a la derecha en 1. Por lo tanto, la string S se modifica de «gabcdef» a «fgabcde».
[0, 2] se refiere a desplazar S[0] a la izquierda en 2. Por lo tanto, la string S se modifica de «fgabcde» a «abcdefg».
[1, 3] se refiere a desplazar S[0] a la derecha en 3. Por lo tanto, la string S se modifica de «abcdefg» a «efgabcd».

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array shift[][] y desplazar S[0] por cantidad de índices en la dirección especificada. Después de completar todas las operaciones de cambio, imprima la string final obtenida.
Tiempo Complejidad: O(N ² )
Espacio auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación:

• Inicialice una variable, digamos val, para almacenar los turnos efectivos.
• Recorra la array shift[][] y realice las siguientes operaciones en cada i ^-ésima fila:
• Si shift[i][0] = 0 ( desplazamiento a la izquierda ) , entonces disminuya val en -shift[i][1].
• De lo contrario ( desplazamiento a la izquierda ), aumente val por shift[i][1].
• Actualice val = val % len (para optimizar aún más los turnos efectivos).
• Inicialice una string , resultado = “” , para almacenar la string modificada.
• Ahora, comprueba si val > 0 . Si se determina que es cierto, realice la rotación correcta en la string mediante val .
• De lo contrario, realice la rotación a la izquierda de la string mediante |val| Monto.
• Imprime el resultado.

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 find the string obtained
// after performing given shift operations
void stringShift(string s,
                 vector<vector<int> >& shift)
{
 
    int val = 0;
 
    for (int i = 0; i < shift.size(); ++i)
 
        // If shift[i][0] = 0, then left shift
        // Otherwise, right shift
        val += shift[i][0] == 0
                   ? -shift[i][1]
                   : shift[i][1];
 
    // Stores length of the string
    int len = s.length();
 
    // Effective shift calculation
    val = val % len;
 
    // Stores modified string
    string result = "";
 
    // Right rotation
    if (val > 0)
        result = s.substr(len - val, val)
                 + s.substr(0, len - val);
 
    // Left rotation
    else
        result
            = s.substr(-val, len + val)
              + s.substr(0, -val);
 
    cout << result;
}
 
// Driver Code
int main()
{
    string s = "abc";
    vector<vector<int> > shift = {
        { 0, 1 },
        { 1, 2 }
    };
 
    stringShift(s, shift);
 
    return 0;
}

cab

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

¡ Consulte el artículo completo sobre Modificar una string realizando operaciones de cambio dadas para obtener más detalles!