Dadas dos strings S 1 y S 2 de longitud N y un entero positivo K , la tarea es encontrar la string lexicográficamente más pequeña tal que difiera de las dos strings S 1 y S 2 dadas exactamente en K lugares. Si no existe tal string, imprima «-1» .
Ejemplos:
Entrada: N = 4, K = 3, S 1 = “ccbb”, S 2 = “caab”
Salida: abcb
Explicación:
La string “abcb” difiere de S 1 exactamente en 3 lugares, es decir, en las posiciones 1, 2 y 3, y
la string «abcb» difiere de S 2 exactamente en 3 lugares, es decir, en las posiciones 1, 2 y 3.
Entrada: N = 5, K = 1, S 1 = «cbabb», S 2 = «babaa»
Salida: -1
Explicación:
No existe tal string que difiera simultáneamente de S 1 y S 2 solo en 1 posición.
Acercarse:
- En lugar de construir S 3 desde cero, elija S 2 como la string resultante S 3 e intente modificarla de acuerdo con las restricciones dadas.
- Encuentre en cuántas posiciones la string de respuesta S 3 difiere de S 1 .
- Que se diferencien entre sí exactamente en d posiciones. Entonces, el número mínimo de lugares en los que la string de respuesta S 3 puede diferir de ambas strings es ceil(d/2) y el número máximo de lugares puede ser N .
- Si K está dentro del rango [ceil(d/2), N], entonces S 3 existe; de lo contrario, S 3 no existe e imprime “-1” .
- Para la string S 3 a continuación se muestran los casos:
- K mayor que d
- Si K es mayor que d, modifique todas las posiciones en las que S 1 difiere de S 3 de modo que, después de la modificación, S 3 en esa posición difiera ahora de S 1 y S 2 . Decremento K.
- Modifique las posiciones en las que S 1 es igual a S 3 de modo que, después de la modificación, S 3 en esa posición difiera ahora de S 1 y S 2 . Decremento K.
- K menor o igual que d
- En este caso, modifique únicamente la posición S 3 en la que S 1 y S 3 difieren.
- Después de la modificación, sea X el número de posiciones en las que sólo S 1 difiere de S 3 y S 2 difiere de S 3 .
- Sea T el número de posiciones en las que tanto S 1 como S 2 difieren de S 3 . Entonces la ecuación será:
- K mayor que d
(2 * X) + T = re
X + T = K
- Resolviendo estas ecuaciones, se pueden obtener los valores de X y T y modificar la string de respuesta S 3 en consecuencia.
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;
char arr[] = { 'a', 'b', 'c' };
// Function to find the string which
// differ at exactly K positions
void findString(int n, int k,
string s1, string s2)
{
// Initialise s3 as s2
string s3 = s2;
// Number of places at which
// s3 differ from s2
int d = 0;
for (int i = 0;
i < s1.size(); i++) {
if (s1[i] != s2[i])
d++;
}
// Minimum possible value
// is ceil(d/2) if it is
// not possible then -1
if ((d + 1) / 2 > k) {
cout << "-1" << endl;
return;
}
else {
// Case 2 when K is
// less equal d
if (k <= d) {
// value of X and T
// after solving
// equations
// T shows the number
// of modification
// such that position
// differ from both
// X show the modification
// such that this position
// only differ from only
// one string
int X = d - k;
int T = 2 * k - d;
for (int i = 0;
i < s3.size(); i++) {
if (s1[i] != s2[i]) {
// modify the position
// such that this
// differ from both
// S1 & S2 & decrease
// the T at each step
if (T > 0) {
// Finding the character
// which is different
// from both S1 and S2
for (int j = 0;
j < 3; j++) {
if (arr[j] != s1[i]
&& arr[j] != s2[i]) {
s3[i] = arr[j];
T--;
break;
}
}
}
// After we done T
// start modification
// to meet our
// requirement
// for X type
else if (X > 0) {
s3[i] = s1[i];
X--;
}
}
}
// Resultant string
cout << s3 << endl;
}
else {
// Case 1 when K > d
// In first step, modify all
// the character which are
// not same in S1 and S3
for (int i = 0;
i < s1.size(); i++) {
if (s1[i] != s3[i]) {
for (int j = 0;
j < 3; j++) {
// Finding character
// which is
// different from
// both S1 and S2
if (arr[j] != s1[i]
&& arr[j] != s3[i]) {
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Our requirement not
// satisfied by performing
// step 1. We need to
// modify the position
// which matches in
// both string
for (int i = 0;
i < s1.size(); i++) {
if (s1[i] == s3[i] && k) {
// Finding the character
// which is different
// from both S1 and S2
for (int j = 0; j < 3; j++) {
if (arr[j] != s1[i]
&& arr[j] != s3[i]) {
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Resultant string
cout << s3 << endl;
}
}
}
// Driver Code
int main()
{
int N = 4, k = 2;
// Given two strings
string S1 = "zzyy";
string S2 = "zxxy";
// Function Call
findString(N, k, S1, S2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static char arr[] = { 'a', 'b', 'c' };
// Function to find the String which
// differ at exactly K positions
static void findString(int n, int k,
char []s1,
char []s2)
{
// Initialise s3 as s2
char []s3 = s2;
// Number of places at which
// s3 differ from s2
int d = 0;
for (int i = 0;
i < s1.length; i++)
{
if (s1[i] != s2[i])
d++;
}
// Minimum possible value
// is Math.ceil(d/2) if it is
// not possible then -1
if ((d + 1) / 2 > k)
{
System.out.print("-1" + "\n");
return;
}
else
{
// Case 2 when K is
// less equal d
if (k <= d)
{
// value of X and T
// after solving
// equations
// T shows the number
// of modification
// such that position
// differ from both
// X show the modification
// such that this position
// only differ from only
// one String
int X = d - k;
int T = 2 * k - d;
for (int i = 0; i < s3.length; i++)
{
if (s1[i] != s2[i])
{
// modify the position
// such that this
// differ from both
// S1 & S2 & decrease
// the T at each step
if (T > 0)
{
// Finding the character
// which is different
// from both S1 and S2
for (int j = 0; j < 3; j++)
{
if (arr[j] != s1[i] &&
arr[j] != s2[i])
{
s3[i] = arr[j];
T--;
break;
}
}
}
// After we done T
// start modification
// to meet our
// requirement
// for X type
else if (X > 0)
{
s3[i] = s1[i];
X--;
}
}
}
// Resultant String
System.out.print(new String(s3) + "\n");
}
else
{
// Case 1 when K > d
// In first step, modify all
// the character which are
// not same in S1 and S3
for (int i = 0;
i < s1.length; i++)
{
if (s1[i] != s3[i])
{
for (int j = 0;
j < 3; j++)
{
// Finding character
// which is
// different from
// both S1 and S2
if (arr[j] != s1[i] &&
arr[j] != s3[i])
{
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Our requirement not
// satisfied by performing
// step 1. We need to
// modify the position
// which matches in
// both String
for (int i = 0;
i < s1.length; i++)
{
if (s1[i] == s3[i] && k > 0)
{
// Finding the character
// which is different
// from both S1 and S2
for (int j = 0; j < 3; j++)
{
if (arr[j] != s1[i] &&
arr[j] != s3[i])
{
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Resultant String
System.out.print(new String(s3) + "\n");
}
}
}
// Driver Code
public static void main(String[] args)
{
int N = 4, k = 2;
// Given two Strings
String S1 = "zzyy";
String S2 = "zxxy";
// Function Call
findString(N, k, S1.toCharArray(), S2.toCharArray());
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach
arr = [ 'a', 'b', 'c' ]
# Function to find the string which
# differ at exactly K positions
def findString(n, k, s1, s2):
# Initialise s3 as s2
s3 = s2
s3 = list(s3)
# Number of places at which
# s3 differ from s2
d = 0
for i in range(len(s1)):
if (s1[i] != s2[i]):
d += 1
# Minimum possible value
# is ceil(d/2) if it is
# not possible then -1
if ((d + 1) // 2 > k):
print ("-1")
return
else:
# Case 2 when K is
# less equal d
if (k <= d):
# Value of X and T
# after solving
# equations
# T shows the number
# of modification
# such that position
# differ from both
# X show the modification
# such that this position
# only differ from only
# one string
X = d - k
T = 2 * k - d
for i in range(len(s3)):
if (s1[i] != s2[i]):
# Modify the position
# such that this
# differ from both
# S1 & S2 & decrease
# the T at each step
if (T > 0):
# Finding the character
# which is different
# from both S1 and S2
for j in range(3):
if (arr[j] != s1[i] and
arr[j] != s2[i]):
s3[i] = arr[j]
T -= 1
break
# After we done T
# start modification
# to meet our
# requirement
# for X type
elif (X > 0):
s3[i] = s1[i]
X -= 1
# Resultant string
print("".join(s3))
else:
# Case 1 when K > d
# In first step, modify all
# the character which are
# not same in S1 and S3
for i in range(len(s1)):
if (s1[i] != s3[i]):
for j in range(3):
# Finding character
# which is
# different from
# both S1 and S2
if (arr[j] != s1[i] and
arr[j] != s3[i]):
s3[i] = arr[j]
k -= 1
break
# Our requirement not
# satisfied by performing
# step 1. We need to
# modify the position
# which matches in
# both string
for i in range(len(s1)):
if (s1[i] == s3[i] and k):
# Finding the character
# which is different
# from both S1 and S2
for j in range (3):
if (arr[j] != s1[i] and
arr[j] != s3[i]):
s3[i] = arr[j]
k -= 1
break
# Resultant string
print("".join(s3))
# Driver Code
if __name__ == "__main__":
N = 4
k = 2
# Given two strings
S1 = "zzyy"
S2 = "zxxy"
# Function call
findString(N, k, S1, S2)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
static char []arr = { 'a', 'b', 'c' };
// Function to find the String which
// differ at exactly K positions
static void findString(int n, int k,
char []s1,
char []s2)
{
// Initialise s3 as s2
char []s3 = s2;
// Number of places at which
// s3 differ from s2
int d = 0;
for(int i = 0;
i < s1.Length; i++)
{
if (s1[i] != s2[i])
d++;
}
// Minimum possible value
// is Math.Ceiling(d/2) if it is
// not possible then -1
if ((d + 1) / 2 > k)
{
Console.Write("-1" + "\n");
return;
}
else
{
// Case 2 when K is
// less equal d
if (k <= d)
{
// Value of X and T
// after solving
// equations
// T shows the number
// of modification
// such that position
// differ from both
// X show the modification
// such that this position
// only differ from only
// one String
int X = d - k;
int T = 2 * k - d;
for(int i = 0; i < s3.Length; i++)
{
if (s1[i] != s2[i])
{
// Modify the position
// such that this
// differ from both
// S1 & S2 & decrease
// the T at each step
if (T > 0)
{
// Finding the character
// which is different
// from both S1 and S2
for(int j = 0; j < 3; j++)
{
if (arr[j] != s1[i] &&
arr[j] != s2[i])
{
s3[i] = arr[j];
T--;
break;
}
}
}
// After we done T start
// modification to meet our
// requirement for X type
else if (X > 0)
{
s3[i] = s1[i];
X--;
}
}
}
// Resultant String
Console.Write(new String(s3) + "\n");
}
else
{
// Case 1 when K > d
// In first step, modify all
// the character which are
// not same in S1 and S3
for(int i = 0; i < s1.Length; i++)
{
if (s1[i] != s3[i])
{
for(int j = 0; j < 3; j++)
{
// Finding character
// which is different
// from both S1 and S2
if (arr[j] != s1[i] &&
arr[j] != s3[i])
{
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Our requirement not
// satisfied by performing
// step 1. We need to
// modify the position
// which matches in
// both String
for(int i = 0; i < s1.Length; i++)
{
if (s1[i] == s3[i] && k > 0)
{
// Finding the character
// which is different
// from both S1 and S2
for(int j = 0; j < 3; j++)
{
if (arr[j] != s1[i] &&
arr[j] != s3[i])
{
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Resultant String
Console.Write(new String(s3) + "\n");
}
}
}
// Driver Code
public static void Main(String[] args)
{
int N = 4, k = 2;
// Given two Strings
String S1 = "zzyy";
String S2 = "zxxy";
// Function Call
findString(N, k, S1.ToCharArray(),
S2.ToCharArray());
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// javascript program for the above approach
var arr = [ 'a', 'b', 'c' ];
// Function to find the String which
// differ at exactly K positions
function findString(n , k,s1,s2)
{
// Initialise s3 as s2
var s3 = s2;
// Number of places at which
// s3 differ from s2
var d = 0;
for (i = 0;
i < s1.length; i++)
{
if (s1[i] != s2[i])
d++;
}
// Minimum possible value
// is Math.ceil(d/2) if it is
// not possible then -1
if ((d + 1) / 2 > k)
{
document.write("-1" + "<br>");
return;
}
else
{
// Case 2 when K is
// less equal d
if (k <= d)
{
// value of X and T
// after solving
// equations
// T shows the number
// of modification
// such that position
// differ from both
// X show the modification
// such that this position
// only differ from only
// one String
var X = d - k;
var T = 2 * k - d;
for (i = 0; i < s3.length; i++)
{
if (s1[i] != s2[i])
{
// modify the position
// such that this
// differ from both
// S1 & S2 & decrease
// the T at each step
if (T > 0)
{
// Finding the character
// which is different
// from both S1 and S2
for (j = 0; j < 3; j++)
{
if (arr[j] != s1[i] &&
arr[j] != s2[i])
{
s3[i] = arr[j];
T--;
break;
}
}
}
// After we done T
// start modification
// to meet our
// requirement
// for X type
else if (X > 0)
{
s3[i] = s1[i];
X--;
}
}
}
// Resultant String
document.write(s3.join('') + "<br>");
}
else
{
// Case 1 when K > d
// In first step, modify all
// the character which are
// not same in S1 and S3
for (i = 0;
i < s1.length; i++)
{
if (s1[i] != s3[i])
{
for (j = 0;
j < 3; j++)
{
// Finding character
// which is
// different from
// both S1 and S2
if (arr[j] != s1[i] &&
arr[j] != s3[i])
{
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Our requirement not
// satisfied by performing
// step 1. We need to
// modify the position
// which matches in
// both String
for (i = 0;
i < s1.length; i++)
{
if (s1[i] == s3[i] && k > 0)
{
// Finding the character
// which is different
// from both S1 and S2
for (j = 0; j < 3; j++)
{
if (arr[j] != s1[i] &&
arr[j] != s3[i])
{
s3[i] = arr[j];
k--;
break;
}
}
}
}
// Resultant String
document.write(s3.join('') + "<br>");
}
}
}
// Driver Code
var N = 4, k = 2;
// Given two Strings
var S1 = "zzyy";
var S2 = "zxxy";
// Function Call
findString(N, k, S1.split(''), S2.split(''));
// This code is contributed by 29AjayKumar
</script>
Producción:
zaay
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por AyushMalik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA