Dadas dos strings , str1 y str2 de longitud N , la tarea es convertir la string str1 a la string str2 seleccionando una substring y reemplazando todos los caracteres presentes en los índices pares de la substring por cualquier carácter posible, un número par de veces.
Ejemplos:
Entrada: str1 = “abcdef”, str2 = “ffffff”
Salida: 2
Explicación:
Seleccionar la substring {str1[0], …, str[4]} y reemplazar todos los índices pares de la substring por ‘f’ modifica str1 a “fbfdff”.
Seleccionar la substring {str1[1], …, str[3]} y reemplazar todos los índices pares de la substring por ‘f’ modifica str1 a “ffffff”, que es lo mismo que str2.
Por lo tanto, la salida requerida es 2.Entrada: str1 = “rtrtyy”, str2 = “wtwtzy”
Salida: 1
Explicación:
Seleccionar la substring {str1[0], …, str[4]} y reemplazar str1[0] por ‘w’, str1[[2] por ‘w’ y str[4] por ‘t’ modifica str1 a «wtwtzy», que es lo mismo que str2. Por lo tanto, la salida requerida es 1.
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntOp , para almacenar el recuento mínimo de operaciones dadas requeridas para convertir la string str1 a str2 .
- Iterar sobre los caracteres de la string . Para cada i -ésimo índice, verifique si str1[i] y str2[i] son iguales o no. Si se encuentra que es diferente, busque la substring más larga posible que contenga diferentes caracteres en índices pares en ambas strings. Reemplace incluso los caracteres indexados de esa substring de str1 e incremente el valor de cntOp en 1 .
- Finalmente, imprima el valor de cntOp .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the minimum number of
// substrings of str1 such that replacing
// even-indexed characters of those substrings
// converts the string str1 to str2
int minOperationsReq(string str1, string str2)
{
// Stores length of str1
int N = str1.length();
// Stores minimum count of operations
// to convert str1 to str2
int cntOp = 0;
// Traverse both the given string
for (int i = 0; i < N; i++) {
// If current character in
// both the strings are equal
if (str1[i] == str2[i]) {
continue;
}
// Stores current index
// of the string
int ptr = i;
// If current character in both
// the strings are not equal
while (ptr < N && str1[ptr] != str2[ptr]) {
// Replace str1[ptr]
// by str2[ptr]
str1[ptr] = str2[ptr];
// Update ptr
ptr += 2;
}
// Update cntOp
cntOp++;
}
return cntOp;
}
// Driver Code
int main()
{
string str1 = "abcdef";
string str2 = "ffffff";
cout << minOperationsReq(str1, str2);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG {
// Function to count the minimum number of
// substrings of str1 such that replacing
// even-indexed characters of those substrings
// converts the string str1 to str2
static int min_Operations(String str1,
String str2)
{
// Stores length of str1
int N = str1.length();
// Convert str1 to character array
char[] str = str1.toCharArray();
// Stores minimum count of operations
// to convert str1 to str2
int cntOp = 0;
// Traverse both the given string
for (int i = 0; i < N; i++) {
// If current character in both
// the strings are equal
if (str[i] == str2.charAt(i)) {
continue;
}
// Stores current index
// of the string
int ptr = i;
// If current character in both the
// string are not equal
while (ptr < N && str[ptr] != str2.charAt(ptr)) {
// Replace str1[ptr]
// by str2[ptr]
str[ptr] = str2.charAt(ptr);
// Update ptr
ptr += 2;
}
// Update cntOp
cntOp++;
}
return cntOp;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "abcdef";
String str2 = "ffffff";
System.out.println(
min_Operations(str1, str2));
}
}
Python3
# Python3 program to implement # the above approach # Function to count the minimum number of # substrings of str1 such that replacing # even-indexed characters of those substrings # converts the str1 to str2 def minOperationsReq(str11, str22): str1 = list(str11) str2 = list(str22) # Stores length of str1 N = len(str1) # Stores minimum count of operations # to convert str1 to str2 cntOp = 0 # Traverse both the given string for i in range(N): # If current character in # both the strings are equal if (str1[i] == str2[i]): continue # Stores current index # of the string ptr = i # If current character in both # the strings are not equal while (ptr < N and str1[ptr] != str2[ptr]): # Replace str1[ptr] # by str2[ptr] str1[ptr] = str2[ptr] # Update ptr ptr += 2 # Update cntOp cntOp += 1 return cntOp # Driver Code str1 = "abcdef" str2 = "ffffff" print(minOperationsReq(str1, str2)) # This code is contributed by code_hunt
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to count the minimum number of
// substrings of str1 such that replacing
// even-indexed characters of those substrings
// converts the string str1 to str2
static int min_Operations(String str1,
String str2)
{
// Stores length of str1
int N = str1.Length;
// Convert str1 to character array
char[] str = str1.ToCharArray();
// Stores minimum count of operations
// to convert str1 to str2
int cntOp = 0;
// Traverse both the given string
for (int i = 0; i < N; i++)
{
// If current character in both
// the strings are equal
if (str[i] == str2[i])
{
continue;
}
// Stores current index
// of the string
int ptr = i;
// If current character in both the
// string are not equal
while (ptr < N && str[ptr] != str2[ptr])
{
// Replace str1[ptr]
// by str2[ptr]
str[ptr] = str2[ptr];
// Update ptr
ptr += 2;
}
// Update cntOp
cntOp++;
}
return cntOp;
}
// Driver Code
public static void Main(String[] args)
{
String str1 = "abcdef";
String str2 = "ffffff";
Console.WriteLine(
min_Operations(str1, str2));
}
}
// This code contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count the minimum number of
// substrings of str1 such that replacing
// even-indexed characters of those substrings
// converts the string str1 to str2
function min_Operations( str1, str2)
{
// Stores length of str1
var N = str1.length;
// Stores minimum count of operations
// to convert str1 to str2
var cntOp = 0;
// Traverse both the given string
for (var i = 0; i < N; i++) {
// If current character in
// both the strings are equal
if (str1.charCodeAt(i)== str2.charCodeAt(i))
{
continue;
}
// Stores current index
// of the string
var ptr = i;
// If current character in both
// the strings are not equal
while (ptr < N && str1[ptr] != str2[ptr]) {
// Replace str1[ptr]
// by str2[ptr]
str1 = str1.substring(0, ptr) + str2[ptr]
+ str1.substring(ptr + 1);
// Update ptr
ptr += 2;
}
// Update cntOp
cntOp++;
}
return cntOp;
}
// Driver Code
str1 = "abcdef";
str2 = "ffffff";
document.write(min_Operations(str1, str2));
// This code is contributed by todaysgaurav
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA