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 S e insertarlo 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 2 )
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++
// 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;
}
Java
// Java implementation
// of above approach
import java.io.*;
class GFG
{
// Function to find the string obtained
// after performing given shift operations
static void stringShift(String s, int[][] shift)
{
int val = 0;
for (int i = 0; i < shift.length; ++i)
// If shift[i][0] = 0, then left shift
// Otherwise, right shift
if (shift[i][0] == 0)
val -= shift[i][1];
else
val += 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.substring(len - val, (len - val) + val)
+ s.substring(0, len - val);
// Left rotation
else
result = s.substring(-val, len + val)
+ s.substring(0, -val);
System.out.println(result);
}
// Driver Code
public static void main(String[] args)
{
String s = "abc";
int[][] shift
= new int[][] {{ 0, 1 }, { 1, 2 }};
stringShift(s, shift);
}
}
// This code is contributed by Dharanendra L V
C#
// C# implementation
// of above approach
using System;
public class GFG
{
// Function to find the string obtained
// after performing given shift operations
static void stringShift(String s, int[,] shift)
{
int val = 0;
for (int i = 0; i < shift.GetLength(0); ++i)
// If shift[i,0] = 0, then left shift
// Otherwise, right shift
if (shift[i,0] == 0)
val -= shift[i, 1];
else
val += 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.Substring(len - val, val)
+ s.Substring(0, len - val);
// Left rotation
else
result = s.Substring(-val, len)
+ s.Substring(0, -val);
Console.WriteLine(result);
}
// Driver Code
public static void Main(String[] args)
{
String s = "abc";
int[,] shift
= new int[,] {{ 0, 1 }, { 1, 2 }};
stringShift(s, shift);
}
}
// This code contributed by shikhasingrajput
Python3
# Python implementation # of above approach # Function to find the string obtained # after performing given shift operations def stringShift(s, shift): val = 0 for i in range(len(shift)): # If shift[i][0] = 0, then left shift # Otherwise, right shift val += -shift[i][1] if shift[i][0] == 0 else shift[i][1] # Stores length of the string Len = len(s) # Effective shift calculation val = val % Len # Stores modified string result = "" # Right rotation if (val > 0): result = s[Len - val:Len] + s[0: Len - val] # Left rotation else: result = s[-val: Len] + s[0: -val] print(result) # Driver Code s = "abc" shift = [ [ 0, 1 ], [ 1, 2 ] ] stringShift(s, shift) # This code is contributed by shinjanpatra
Javascript
<script>
// Javascript implementation
// of above approach
// Function to find the string obtained
// after performing given shift operations
function stringShift(s, shift)
{
var val = 0;
for (var i = 0; i < shift.length; ++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
var len = s.length;
// Effective shift calculation
val = val % len;
// Stores modified string
var result = "";
// Right rotation
if (val > 0)
result = s.substring(len - val,len)
+ s.substring(0, len - val);
// Left rotation
else
result
= s.substring(-val, len )
+ s.substring(0, -val);
document.write( result);
}
// Driver Code
var s = "abc";
var shift = [
[ 0, 1 ],
[ 1, 2 ]
];
stringShift(s, shift);
// This code is contributed by importantly.
</script>
cab
Complejidad temporal: O(N)
Espacio auxiliar: O(N)