Dada una string S y dos enteros positivos X e Y , la tarea es encontrar el número mínimo de operaciones requeridas para obtener la string original. En cada operación, agregue los caracteres X o Y desde el final de la string al principio de la string, respectivamente, en cada operación.
Ejemplos:
Entrada: S = «GeeksforGeeks», X = 5, Y = 3
Salida: 3
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: agregue 5 caracteres desde la parte posterior de la string S hasta el frente de la string S. Ahora la actualización la string es «GeeksGeeksfor».
Operación 2: agregue 3 caracteres desde la parte posterior de la string S hasta el frente de la string S. Ahora la string actualizada es «forGeeksGeeks».
Operación 3: agregue 5 caracteres desde la parte posterior de la string S hasta el frente de la string S. Ahora la string actualizada es «GeeksforGeeks».
Por lo tanto, el recuento mínimo de operaciones requeridas es 3.Entrada: S = «AbcDef», X = 1, Y = 2
Salida: 4
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: agregue 1 carácter desde la parte posterior de la string S hasta el frente de la string S. Ahora la actualización la string es «fAbcDe».
Operación 2: agregue 2 caracteres desde la parte posterior de la string S hasta el frente de la string S. Ahora la string actualizada es «fDeAbc».
Operación 3: agregue 1 carácter desde la parte posterior de la string S hasta el frente de la string S. Ahora la string actualizada es «cfDeAb».
Operación 4: agregue 2 caracteres desde la parte posterior de la string S hasta el frente de la string S. Ahora la string actualizada es «AbcDef».
Por lo tanto, el recuento mínimo de operaciones requeridas es 4.
Enfoque: la idea es agregar los caracteres X e Y de la string dada al principio de la string respectivamente y realizar un seguimiento del recuento de operaciones mientras se realizan las operaciones. A continuación se muestran los pasos:
- Inicialice el conteo como 0 que almacena las operaciones mínimas.
- Almacene la string S dada en otra string (digamos newString ) donde se debe realizar la operación.
- Ahora realice la siguiente operación en newString hasta que sea igual a S :
- Agregue el carácter X desde el final de la string newString e incremente el conteo en 1 .
- Si newString es lo mismo que la string S .
- Agregue el carácter Y desde el final de la string newString e incremente el conteo en 1 .
- Si newString es lo mismo que la string S .
- Después de los pasos anteriores, imprima el valor de la cuenta como el número mínimo de operaciones requeridas.
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 find the minimum operations
// required to get the given string after
// appending m or n characters from the end
// to the front of the string in each operation
int minimumOperations(string orig_str, int m, int n)
{
// Store the original string
string orig = orig_str;
// Stores the count of operations
int turn = 1;
int j = 1;
// Traverse the string
for(auto i : orig_str)
{
// Cut m letters from end
string m_cut = orig_str.substr(
orig_str.length() - m);
orig_str.erase(orig_str.length() - m);
// Add cut m letters to beginning
orig_str = m_cut + orig_str;
// Update j
j = j + 1;
// Check if strings are the same
if (orig != orig_str)
{
turn = turn + 1;
// Cut n letters from end
string n_cut = orig_str.substr(
orig_str.length() - n);
orig_str.erase(orig_str.length() - n);
// Add cut n letters to beginning
orig_str = n_cut + orig_str;
// Update j
j = j + 1;
}
// Check if strings are the same
if (orig == orig_str)
{
break;
}
// Update the turn
turn = turn + 1;
}
cout << turn;
}
// Driver Code
int main()
{
// Given string S
string S = "GeeksforGeeks";
int X = 5, Y = 3;
// Function Call
minimumOperations(S, X, Y);
return 0;
}
// This code is contributed by akhilsaini
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the minimum operations
// required to get the given string after
// appending m or n characters from the end
// to the front of the string in each operation
static void minimumOperations(String orig_str,
int m, int n)
{
// Store the original string
String orig = orig_str;
// Stores the count of operations
int turn = 1;
int j = 1;
// Traverse the string
for(int i = 0; i < orig_str.length(); i++)
{
// Cut m letters from end
String m_cut = orig_str.substring(
orig_str.length() - m);
orig_str = orig_str.substring(
0, orig_str.length() - m);
// Add cut m letters to beginning
orig_str = m_cut + orig_str;
// Update j
j = j + 1;
// Check if strings are the same
if (!orig.equals(orig_str))
{
turn = turn + 1;
// Cut n letters from end
String n_cut = orig_str.substring(
orig_str.length() - n);
orig_str = orig_str.substring(
0, orig_str.length() - n);
// Add cut n letters to beginning
orig_str = n_cut + orig_str;
// Update j
j = j + 1;
}
// Check if strings are the same
if (orig.equals(orig_str))
{
break;
}
// Update the turn
turn = turn + 1;
}
System.out.println( turn );
}
// Driver Code
public static void main(String[] args)
{
// Given string S
String S = "GeeksforGeeks";
int X = 5, Y = 3;
// Function Call
minimumOperations(S, X, Y);
}
}
// This code is contributed by akhilsaini
Python
# Python program for the above approach
# Function to find the minimum operations
# required to get the given string after
# appending m or n characters from the end
# to the front of the string in each operation
def minimumOperations(orig_str, m, n):
# Store the original string
orig = orig_str
# Stores the count of operations
turn = 1
j = 1
# Traverse the string
for i in orig_str:
# Cut m letters from end
m_cut = orig_str[-m:]
orig_str = orig_str.replace(' ', '')[:-m]
# Add cut m letters to beginning
orig_str = m_cut + orig_str
# Update j
j = j + 1
# Check if strings are the same
if orig != orig_str:
turn = turn + 1
# Cut n letters from end
n_cut = orig_str[-n:]
orig_str = orig_str.replace(' ', '')[:-n]
# Add cut n letters to beginning
orig_str = n_cut + orig_str
# Update j
j = j + 1
# Check if strings are the same
if orig == orig_str:
break
# Update the turn
turn = turn + 1
print(turn)
# Driver Code
# Given string S
S = "GeeksforGeeks"
X = 5
Y = 3
# Function Call
minimumOperations(S, X, Y)
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum operations
// required to get the given string after
// appending m or n characters from the end
// to the front of the string in each operation
static void minimumOperations(string orig_str, int m,
int n)
{
// Store the original string
string orig = orig_str;
// Stores the count of operations
int turn = 1;
int j = 1;
// Traverse the string
for(int i = 0; i < orig_str.Length; i++)
{
// Cut m letters from end
string m_cut = orig_str.Substring(
orig_str.Length - m);
orig_str = orig_str.Substring(
0, orig_str.Length - m);
// Add cut m letters to beginning
orig_str = m_cut + orig_str;
// Update j
j = j + 1;
// Check if strings are the same
if (!orig.Equals(orig_str))
{
turn = turn + 1;
// Cut n letters from end
String n_cut = orig_str.Substring(
orig_str.Length - n);
orig_str = orig_str.Substring(
0, orig_str.Length - n);
// Add cut n letters to beginning
orig_str = n_cut + orig_str;
// Update j
j = j + 1;
}
// Check if strings are the same
if (orig.Equals(orig_str))
{
break;
}
// Update the turn
turn = turn + 1;
}
Console.WriteLine(turn);
}
// Driver Code
public static void Main()
{
// Given string S
string S = "GeeksforGeeks";
int X = 5, Y = 3;
// Function Call
minimumOperations(S, X, Y);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum operations
// required to get the given string after
// appending m or n characters from the end
// to the front of the string in each operation
function minimumOperations(orig_str, m, n)
{
// Store the original string
let orig = orig_str;
// Stores the count of operations
let turn = 1;
let j = 1;
// Traverse the string
for(let i = 0; i < orig_str.length; i++)
{
// Cut m letters from end
let m_cut = orig_str.substring(orig_str.length - m);
orig_str = orig_str.substring(0, orig_str.length - m);
// Add cut m letters to beginning
orig_str = m_cut + orig_str;
// Update j
j = j + 1;
// Check if strings are the same
if (orig != orig_str)
{
turn = turn + 1;
// Cut n letters from end
let n_cut = orig_str.substring(orig_str.length - n);
orig_str = orig_str.substring(0, orig_str.length - n);
// Add cut n letters to beginning
orig_str = n_cut + orig_str;
// Update j
j = j + 1;
}
// Check if strings are the same
if (orig == orig_str)
{
break;
}
// Update the turn
turn = turn + 1;
}
document.write(turn);
}
// Given string S
let S = "GeeksforGeeks";
let X = 5, Y = 3;
// Function Call
minimumOperations(S, X, Y);
// This code is contributed by vaibhavrabadiya117.
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)