Dada la string str de longitud N y una array arr[] de enteros, para el elemento de array arr[i]( indexación basada en 1 ) , invierta la substring en índices [arr[i], N – arr[i] + 1] . La tarea es imprimir la string después de cada inversión.
Ejemplos:
Entrada: str = «GeeksforGeeks», arr[] = {2}
Salida : GkeeGrofskees
Explicación:
Para el primer elemento de la array es 2:
Invierta la substring (2, 12). Ahora la string actualizada es «GkeeGrofskees».Entrada: str = “abcdef”, arr[] = {1, 2, 3}
Salida: fbdcea
Explicación:
Para el primer elemento de la array es 1:
Invierta la substring (1, 6). Ahora la string actualizada es «fedcba».
Para el segundo elemento de la array es 2:
invierta la substring (2, 5). Ahora la string actualizada es «fbcdea».
Para el tercer elemento de la array es 3:
invierta la substring (3, 4). Ahora la string actualizada es «fbdcea».
Enfoque ingenuo: el enfoque más simple es atravesar la array dada y para cada elemento de array arr[i] invertir la substring {s[arr[i]], … s[N – arr[i] + 1]} e imprimir la resultante string obtenida después de una actualización.
Complejidad de tiempo: O(N * K), donde N es la longitud de la string y K es la longitud máxima de la substring invertida.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar manteniendo un registro de la cantidad de veces que se ha invertido cualquier carácter en un índice. Si el recuento de inversión es par , entonces el personaje volverá a su lugar original, por lo que no habrá cambios y si el recuento de inversión es impar , entonces el personaje debe intercambiarse. A continuación se muestran los pasos:
- Inicialice una array count[] para almacenar el número de reversiones en cualquier índice de la string.
- Recorre la array dada arr[] e incrementa el recuento de índices count[arr[i]] en 1 .
- Ahora, recorra la array count[] sobre el rango [1, N/2] usando la variable i y haga lo siguiente:
- Actualice el elemento en el índice actual como la suma del índice actual y el anterior.
- Ahora, si el elemento actual count[i] es impar, entonces intercambie str[i] y str[N – i + 1] .
- Imprima la string después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to perform the reversal
// operation on the given string
string modifyString(int A[], string str,
int K)
{
// Size of string
int N = str.size();
// Stores the count of indices
int count[N + 1] = { 0 };
// Count the positions where
// reversals will begin
for (int i = 0; i < K; i++) {
count[A[i]]++;
}
for (int i = 1; i <= N / 2; i++) {
// Store the count of reversals
// beginning at position i
count[i] = count[i] + count[i - 1];
// Check if the count[i] is
// odd the swap the character
if (count[i] & 1) {
swap(str[i - 1], str[N - i]);
}
}
// Return the updated string
return str;
}
// Driver Code
int main()
{
// Given string str
string str = "abcdef";
// Given array of reversing index
int arr[] = { 1, 2, 3 };
int K = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << modifyString(arr, str, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to perform the reversal
// operation on the given String
static String modifyString(int A[], String str,
int K)
{
// Size of String
int N = str.length();
// Stores the count of indices
int count[] = new int[N + 1];
// Count the positions where
// reversals will begin
for(int i = 0; i < K; i++)
{
count[A[i]]++;
}
for(int i = 1; i <= N / 2; i++)
{
// Store the count of reversals
// beginning at position i
count[i] = count[i] + count[i - 1];
// Check if the count[i] is
// odd the swap the character
if ((count[i] & 1) > 0)
{
str = swap(str, i - 1, N - i);
}
}
// Return the updated String
return str;
}
// Swap char of a string
static String swap(String str, int i, int j)
{
char ch[] = str.toCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.valueOf(ch);
}
// Driver Code
public static void main(String[] args)
{
// Given String str
String str = "abcdef";
// Given array of reversing index
int arr[] = { 1, 2, 3 };
int K = arr.length;
// Function Call
System.out.print(modifyString(arr, str, K));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to perform the reversal # operation on the given string def modifyString(A, str, K): # Size of string N = len(str) # Stores the count of indices count = [0] * (N + 1) # Count the positions where # reversals will begin for i in range(K): count[A[i]] += 1 for i in range(1, N // 2 + 1): # Store the count of reversals # beginning at position i count[i] = count[i] + count[i - 1] # Check if the count[i] is # odd the swap the character if (count[i] & 1): str[i - 1], str[N - i] = str[N - i], str[i - 1] # Return the updated string return "".join(str) # Driver Code if __name__ == '__main__': # Given str str1 = "abcdef" str = [i for i in str1] # Given array of reversing index arr = [ 1, 2, 3 ] K = len(arr) # Function Call print(modifyString(arr, str, K)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to perform the reversal
// operation on the given String
static String modifyString(int []A, String str,
int K)
{
// Size of String
int N = str.Length;
// Stores the count of indices
int []count = new int[N + 1];
// Count the positions where
// reversals will begin
for(int i = 0; i < K; i++)
{
count[A[i]]++;
}
for(int i = 1; i <= N / 2; i++)
{
// Store the count of reversals
// beginning at position i
count[i] = count[i] + count[i - 1];
// Check if the count[i] is
// odd the swap the character
if ((count[i] & 1) > 0)
{
str = swap(str, i - 1, N - i);
}
}
// Return the updated String
return str;
}
// Swap char of a string
static String swap(String str, int i, int j)
{
char []ch = str.ToCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.Join("", ch);
}
// Driver Code
public static void Main(String[] args)
{
// Given String str
String str = "abcdef";
// Given array of reversing index
int []arr = { 1, 2, 3 };
int K = arr.Length;
// Function Call
Console.Write(modifyString(arr, str, K));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to perform the reversal
// operation on the given String
function modifyString(A, str, K) {
// Size of String
str = str.split("")
let N = str.length;
// Stores the count of indices
let count = new Array(N + 1).fill(0);
// Count the positions where
// reversals will begin
for (let i = 0; i < K; i++) {
count[A[i]] += 1;
}
for (let i = 1; i <= N / 2; i++) {
// Store the count of reversals
// beginning at position i
count[i] = count[i] + count[i - 1];
// Check if the count[i] is
// odd the swap the character
if (count[i] & 1) {
let temp = str[i - 1];
str[i - 1] = str[N - i];
str[N - i] = temp
}
}
// Return the updated String
return str.join("");
}
// Driver Code
// Given String str
let str = "abcdef";
// Given array of reversing index
let arr = [1, 2, 3];
let K = arr.length;
// Function Call
document.write(modifyString(arr, str, K));
// This code is contributed by gfgking
</script>
fbdcea
Complejidad de tiempo: O(N + K), donde N es la longitud de la string y K es la longitud máxima de la substring invertida.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ashishsonam00 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA