Dadas dos strings S1 y S2 de la misma longitud. La tarea es encontrar la suma de la diferencia mínima y máxima entre dos strings dadas si se le permite reemplazar el carácter ‘+’ en las strings con cualquier otro carácter.
Nota: si dos strings tienen los mismos caracteres en todos los índices, la diferencia entre ellas es cero.
Ejemplos:
Entrada: S1 = “a+c”, S2 = “++b”
Salida: 4
Explicación:
Diferencia mínima = 1. Para diferencia mínima:
En la string S1 = “a+c”, el “+” puede ser reemplazado por “b”, lo que hace que S1 = “abc”
En la string S2 = “++b”, el “++” se puede reemplazar por “ab”, lo que hace que S2 = “abb”
Arriba, solo el tercer índice tiene un carácter diferente . Entonces, la diferencia mínima = 1
Diferencia máxima = 1. Para diferencia máxima:
En la string S1 = “a+c”, el “+” puede ser reemplazado por “z” haciendo así S1 = “azc”
En la string S2 = “++b”, el “++” se puede reemplazar por “bz”, lo que hace que S2 = “bzb”
Arriba, todos los índices tienen los caracteres de diferencia. Entonces, la diferencia máxima = 3
Diferencia mínima + Diferencia máxima = 1 + 3 = 4
Entrada: S1 = “+++a”, S2 = “+++a”
Salida: 3
Explicación:
Diferencia mínima = 0. Para diferencia mínima:
En la string S1 = “ +++a”, el “+++” se puede reemplazar por “aaa”, lo que hace que S1 = “aaaa”
En la string S2 = “+++a”, el “+++” se puede reemplazar por “aaa ” por lo que S2 = “aaaa”
Arriba, todos los índices tienen los mismos caracteres. Entonces, la diferencia mínima = 0
Diferencia máxima = 3. Para diferencia máxima:
En la string S1 = “+++a”, el “+++” puede ser reemplazado por “aaa” haciendo S1 = “aaaa”
En el string S2 = “+++a”, el “+++” se puede reemplazar por “bbb”, lo que hace que S2 = “bbba”
Arriba, todos los índices excepto el último tienen los caracteres de diferencia. Entonces, la diferencia máxima = 3
Diferencia mínima + Diferencia máxima = 0 + 3 = 3
Acercarse:
- Diferencia mínima: para obtener la diferencia mínima entre las strings, todas las apariciones de «+» se pueden reemplazar por el mismo carácter. Por lo tanto, si hay un «+» en cualquier posición, ese índice específico se puede igualar a la otra string. Por lo tanto, solo contamos el número de índices donde el carácter no es «+» en ninguna de las strings y los caracteres que no son iguales.
- Diferencia máxima: para obtener la diferencia máxima entre las strings, todas las apariciones de «+» se pueden reemplazar por el carácter diferente. Por lo tanto, si hay un «+» en cualquier posición, ese índice específico se puede reemplazar con un carácter diferente al presente en la segunda string. Por lo tanto, contamos el número de índices donde el carácter es «+» en cualquiera de las strings y los caracteres que no son iguales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of the
// minimum and the maximum difference
// between two given strings
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of the
// minimum and the maximum difference
// between two given strings
void solve(string a, string b)
{
int l = a.length();
// Variables to store the minimum
// difference and the maximum difference
int min = 0, max = 0;
// Iterate through the length of the string as
// both the given strings are of the same length
for (int i = 0; i < l; i++) {
// For the maximum difference, we can replace
// "+" in both the strings with different char
if (a[i] == '+' || b[i] == '+' || a[i] != b[i])
max++;
// For the minimum difference, we can replace
// "+" in both the strings with the same char
if (a[i] != '+' && b[i] != '+' && a[i] != b[i])
min++;
}
cout << min + max << endl;
}
// Driver code
int main()
{
string s1 = "a+c", s2 = "++b";
solve(s1, s2);
return 0;
}
Java
// Java program to find the sum of the
// minimum and the maximum difference
// between two given Strings
class GFG{
// Function to find the sum of the
// minimum and the maximum difference
// between two given Strings
static void solve(char []a, char []b)
{
int l = a.length;
// Variables to store the minimum
// difference and the maximum difference
int min = 0, max = 0;
// Iterate through the length of the String as
// both the given Strings are of the same length
for (int i = 0; i < l; i++) {
// For the maximum difference, we can replace
// "+" in both the Strings with different char
if (a[i] == '+' || b[i] == '+' || a[i] != b[i])
max++;
// For the minimum difference, we can replace
// "+" in both the Strings with the same char
if (a[i] != '+' && b[i] != '+' && a[i] != b[i])
min++;
}
System.out.print(min + max +"\n");
}
// Driver code
public static void main(String[] args)
{
String s1 = "a+c", s2 = "++b";
solve(s1.toCharArray(), s2.toCharArray());
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the sum of the # minimum and the maximum difference # between two given strings # Function to find the sum of the # minimum and the maximum difference # between two given strings def solve(a, b): l = len(a) # Variables to store the minimum # difference and the maximum difference min = 0 max = 0 # Iterate through the length of the as # both the given strings are of the same length for i in range(l): # For the maximum difference, we can replace # "+" in both the strings with different char if (a[i] == '+' or b[i] == '+' or a[i] != b[i]): max += 1 # For the minimum difference, we can replace # "+" in both the strings with the same char if (a[i] != '+' and b[i] != '+' and a[i] != b[i]): min += 1 print(min + max) # Driver code if __name__ == '__main__': s1 = "a+c" s2 = "++b" solve(s1, s2) # This code is contributed by mohit kumar 29
C#
// C# program to find the sum of the
// minimum and the maximum difference
// between two given Strings
using System;
class GFG{
// Function to find the sum of the
// minimum and the maximum difference
// between two given Strings
static void solve(char []a, char []b)
{
int l = a.Length;
// Variables to store the minimum
// difference and the maximum difference
int min = 0, max = 0;
// Iterate through the length of the String as
// both the given Strings are of the same length
for (int i = 0; i < l; i++) {
// For the maximum difference, we can replace
// "+" in both the Strings with different char
if (a[i] == '+' || b[i] == '+' || a[i] != b[i])
max++;
// For the minimum difference, we can replace
// "+" in both the Strings with the same char
if (a[i] != '+' && b[i] != '+' && a[i] != b[i])
min++;
}
Console.Write(min + max +"\n");
}
// Driver code
public static void Main(String[] args)
{
String s1 = "a+c", s2 = "++b";
solve(s1.ToCharArray(), s2.ToCharArray());
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the sum of the
// minimum and the maximum difference
// between two given strings
// Function to find the sum of the
// minimum and the maximum difference
// between two given strings
function solve(a, b)
{
var l = a.length;
// Variables to store the minimum
// difference and the maximum difference
var min = 0, max = 0;
// Iterate through the length of the string as
// both the given strings are of the same length
for (var i = 0; i < l; i++) {
// For the maximum difference, we can replace
// "+" in both the strings with different char
if (a[i] == '+' || b[i] == '+' || a[i] != b[i])
max++;
// For the minimum difference, we can replace
// "+" in both the strings with the same char
if (a[i] != '+' && b[i] != '+' && a[i] != b[i])
min++;
}
document.write(min + max);
}
// Driver code
var s1 = "a+c", s2 = "++b";
solve(s1, s2);
</script>
4
Complejidad de tiempo: O(N)