Dadas dos strings S1 y S2 que contienen solo alfabetos ingleses en minúsculas, la tarea es minimizar el número de operaciones requeridas para hacer que S1 contenga solo caracteres de S2 donde en cada operación cualquier carácter de S1 se puede convertir a cualquier otra letra y el costo de la operación será la diferencia entre esas dos letras .
Ejemplos:
Entrada: S1 = “abc”, S2 = “ad”
Salida: 2
Explicación:
No es necesario cambiar el primer carácter de S1, ya que el carácter ‘a’ también está presente en S2.
El segundo carácter de S1 se puede cambiar a ‘a’, ya que para convertirlo en ‘a’ necesita 1 operación y para convertirlo en ‘d’ necesita 2 operaciones.
El tercer carácter de S1 se puede cambiar a ‘d’ para convertirlo en ‘a’ necesita 2 operaciones y para convertirlo en ‘d’ necesita 1 operación.
Entonces, el número mínimo de operaciones para convertir la string «abc» en «aad» necesita 2 operaciones.Entrada: S1 = “aaa”, S2 = “a”
Salida: 0
Explicación: S1 contiene caracteres solo presentes en S2.
Enfoque: La idea es encontrar el número mínimo de operaciones necesarias para convertir cada carácter de S1 en cualquiera de los caracteres de S2 que se aproxime más. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos minOpr como 0 que almacena la cantidad mínima de operaciones requeridas.
- Iterar sobre el rango [0, N1) usando la variable i y realizar los siguientes pasos:
- Compruebe si el carácter S1[i] está presente en el S2. Si no está presente, continúe con la iteración.
- Iterar sobre el rango [0, 26) usando la variable j .
- Verifique si S1[i] es mayor que S2[j] y luego encuentre el mínimo de curMinOpr , (S1[i] – S2[j]) y (26 – (S1[i]-‘a’) + (S2[j] – ‘a’)) y almacene el valor en curMinOpr .
- De lo contrario, busque el mínimo de curMinOpr , (S2[j] – S1[i]) y ((S1[i] – ‘a’) + (26 – (S2[j] – ‘a’))) y almacene el valor en curMinOpr .
- Actualice el valor de minOpr a minOpr += curMinOpr .
- Finalmente, imprima el valor de minOpr .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of
// operations required to make string S1
// contains only characters from the string S2
void minOperations(string S1, string S2,
int N1, int N2)
{
// Stores the minimum of operations
// required
int minOpr = 0;
for (int i = 0; i < N1; i++) {
// Check character S1[i] is not
// present in S2
if (S2.find(S1[i]) != string::npos) {
continue;
}
// Stores the minimum operations required
// for the current character S1[i]
int curMinOpr = INT_MAX;
for (int j = 0; j < N2; j++) {
// Check S1[i] alphabet is greater
// than the S2[j] alphabet
if (S1[i] > S2[j]) {
// Find the minimum operations
// required to make the
// character S1[i] to S2[j]
curMinOpr
= min(curMinOpr,
(min(S1[i] - S2[j],
26 - (S1[i] - 'a')
+ (S2[j] - 'a'))));
}
else {
// Find the minimum operations
// required to make the
// character S1[i] to S2[j]
curMinOpr = min(
curMinOpr,
(min(S2[j] - S1[i],
(S1[i] - 'a')
+ (26 - (S2[j] - 'a')))));
}
}
// Update the value of minOpr
minOpr += curMinOpr;
}
// Print the value of minOpr
cout << minOpr << endl;
}
// Driver code
int main()
{
string S1 = "abc", S2 = "ad";
int N1 = S1.length(), N2 = S2.length();
minOperations(S1, S2, N1, N2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum number of
// operations required to make String S1
// contains only characters from the String S2
static void minOperations(String S1, String S2,
int N1, int N2)
{
// Stores the minimum of operations
// required
int minOpr = 0;
for (int i = 0; i < N1; i++) {
// Check character S1.charAt(i) is not
// present in S2
if (S2.contains(String.valueOf(S1.charAt(i)))) {
continue;
}
// Stores the minimum operations required
// for the current character S1.charAt(i)
int curMinOpr = Integer.MAX_VALUE;
for (int j = 0; j < N2; j++) {
// Check S1.charAt(i) alphabet is greater
// than the S2.charAt(j) alphabet
if (S1.charAt(i) > S2.charAt(j)) {
// Find the minimum operations
// required to make the
// character S1.charAt(i) to S2.charAt(j)
curMinOpr
= Math.min(curMinOpr,
(Math.min(S1.charAt(i) - S2.charAt(j),
26 - (S1.charAt(i) - 'a')
+ (S2.charAt(j) - 'a'))));
}
else {
// Find the minimum operations
// required to make the
// character S1.charAt(i) to S2.charAt(j)
curMinOpr = Math.min(
curMinOpr,
(Math.min(S2.charAt(j) - S1.charAt(i),
(S1.charAt(i) - 'a')
+ (26 - (S2.charAt(j) - 'a')))));
}
}
// Update the value of minOpr
minOpr += curMinOpr;
}
// Print the value of minOpr
System.out.print(minOpr +"\n");
}
// Driver code
public static void main(String[] args)
{
String S1 = "abc", S2 = "ad";
int N1 = S1.length(), N2 = S2.length();
minOperations(S1, S2, N1, N2);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach
def present(S2, c):
for i in range(len(S2)):
if S2[i] == c:
return 1
return 0
# Function to find the minimum number of
# operations required to make string S1
# contains only characters from the string S2
def minOperations(S1, S2, N1, N2):
# Stores the minimum of operations
# required
minOpr = 0
for i in range(N1):
# Check character S1[i] is not
# present in S2
if present(S2, S1[i]):
continue
# Stores the minimum operations required
# for the current character S1[i]
curMinOpr = 10 ** 9
for j in range(N2):
# Check S1[i] alphabet is greater
# than the S2[j] alphabet
if ord(S1[i]) > ord(S2[j]):
# Find the minimum operations
# required to make the
# character S1[i] to S2[j]
curMinOpr = min(
curMinOpr,
(
min(
ord(S1[i]) - ord(S2[j]),
26
- (ord(S1[i]) - ord("a"))
+ (ord(S2[j]) - ord("a")),
)
),
)
else:
# Find the minimum operations
# required to make the
# character S1[i] to S2[j]
curMinOpr = min(
curMinOpr,
(
min(
ord(S2[j]) - ord(S1[i]),
(ord(S1[i]) - ord("a"))
+ (26 - (ord(S2[j]) - ord("a"))),
)
),
)
# Update the value of minOpr
minOpr += curMinOpr
# Print the value of minOpr
print(minOpr)
# Driver code
S1 = "abc"
S2 = "ad"
N1 = len(S1)
N2 = len(S2)
minOperations(S1, S2, N1, N2)
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG
{
static bool present(string S2, char c) {
for (int i = 0; i < S2.Length; i++) {
if (S2[i] == c) {
return true;
}
}
return false;
}
// Function to find the minimum number of
// operations required to make string S1
// contains only characters from the string S2
static void minOperations(string S1, string S2,
int N1, int N2)
{
// Stores the minimum of operations
// required
int minOpr = 0;
for (int i = 0; i < N1; i++) {
// Check character S1[i] is not
// present in S2
if (present(S2, S1[i])) {
continue;
}
// Stores the minimum operations required
// for the current character S1[i]
int curMinOpr = Int32.MaxValue;
for (int j = 0; j < N2; j++) {
// Check S1[i] alphabet is greater
// than the S2[j] alphabet
if (S1[i] > S2[j]) {
// Find the minimum operations
// required to make the
// character S1[i] to S2[j]
curMinOpr
= Math.Min(curMinOpr,
(Math.Min(S1[i] - S2[j],
26 - (S1[i] - 'a')
+ (S2[j] - 'a'))));
}
else {
// Find the minimum operations
// required to make the
// character S1[i] to S2[j]
curMinOpr = Math.Min(
curMinOpr,
(Math.Min(S2[j] - S1[i],
(S1[i] - 'a')
+ (26 - (S2[j] - 'a')))));
}
}
// Update the value of minOpr
minOpr += curMinOpr;
}
// Print the value of minOpr
Console.WriteLine(minOpr);
}
// Driver code
public static void Main()
{
string S1 = "abc", S2 = "ad";
int N1 = S1.Length, N2 = S2.Length;
minOperations(S1, S2, N1, N2);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
function present(S2, c) {
for (let i = 0; i < S2.length; i++) {
if (S2[i] == c) {
return 1;
}
}
return 0;
}
// Function to find the minimum number of
// operations required to make string S1
// contains only characters from the string S2
function minOperations(S1, S2,
N1, N2)
{
// Stores the minimum of operations
// required
let minOpr = 0;
for (let i = 0; i < N1; i++) {
// Check character S1[i] is not
// present in S2
if (present(S2, S1[i])) {
continue;
}
// Stores the minimum operations required
// for the current character S1[i]
let curMinOpr = Number.MAX_VALUE;
for (let j = 0; j < N2; j++) {
// Check S1[i] alphabet is greater
// than the S2[j] alphabet
if (S1[i].charCodeAt(0) > S2[j].charCodeAt(0)) {
// Find the minimum operations
// required to make the
// character S1[i] to S2[j]
curMinOpr
= Math.min(curMinOpr,
(Math.min(S1[i].charCodeAt(0) - S2[j].charCodeAt(0),
26 - (S1[i].charCodeAt(0) - 'a'.charCodeAt(0))
+ (S2[j].charCodeAt(0) - 'a'.charCodeAt(0)))));
}
else {
// Find the minimum operations
// required to make the
// character S1[i] to S2[j]
curMinOpr = Math.min(
curMinOpr,
(Math.min(S2[j].charCodeAt(0) - S1[i].charCodeAt(0),
(S1[i].charCodeAt(0) - 'a'.charCodeAt(0))
+ (26 - (S2[j].charCodeAt(0) - 'a'.charCodeAt(0))))));
}
}
// Update the value of minOpr
minOpr += curMinOpr;
}
// Print the value of minOpr
document.write(minOpr + "<br>")
}
// Driver code
let S1 = "abc", S2 = "ad";
let N1 = S1.length, N2 = S2.length;
minOperations(S1, S2, N1, N2);
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de tiempo: O(N 1 * N 2 ) donde N 1 y N 2 son del tamaño de S1 y S2 respectivamente
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA