Dadas dos strings , str1 y str2 que consisten en N alfabetos en minúsculas, la tarea es encontrar el recuento mínimo de operaciones de los siguientes dos tipos para hacer que ambas strings sean palindrómicas .
- Reemplace cualquier carácter de las strings por cualquier otro carácter ( [a – z] ).
- Intercambie dos caracteres cualesquiera presentes en el mismo índice en ambas strings.
Ejemplos:
Entrada: str1 = “abbd”, str2 = “dbca”
Salida: 2
Explicación:
El intercambio (str1[0], str2[0]) modifica las strings str1 a “dbbd” y str2 a “abca”
Reemplazando str2[1] a ‘ c’ modifica la string str2 a «acca».
Por lo tanto, después de las 2 operaciones anteriores, las strings str1 y str2 se vuelven palindrómicas.Entrada: str1 = «geeksforgeeks», str2 = «geeksforgeeks»
Salida: 10
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos i = 0 y j = 0 para almacenar el índice del puntero izquierdo y el puntero derecho de ambas strings, respectivamente.
- Inicialice una variable, digamos cntOp para almacenar el recuento de operaciones mínimas requeridas para hacer que ambas strings sean palindrómicas .
- Atraviese ambas strings y verifique las siguientes condiciones:
- Si str1[i] == str1[j] y str2[i] != str2[j] , reemplace el valor de str2[i] por str2[j] e incremente el valor de cntOp en 1 .
- Si str1[i] != str1[j] y str2[i] == str2[j] , reemplace el valor de str1[i] por str1[j] e incremente el valor de cntOp en 1 .
- Si str1[i] != str1[j] y str2[i] != str2[j] , compruebe si el valor de (str1[i] == str2[j] y str2[i] == str1[j ]) igual a verdadero o no. Si se determina que es cierto, entonces swap(str1[i], str2[j]) e incrementa el valor de cntOp en 1 .
- De lo contrario, reemplace str1[i] por str1[j] , str2[i] por str2[j] e incremente el valor de cntOp en 2 .
- 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 find minimum operations
// to make both the strings palindromic
int MincntBothPalin(string str1,
string str2, int N)
{
// Stores index of
// the left pointer
int i = 0;
// Stores index of
// the right pointer
int j = N - 1;
// Stores count of minimum operations to
// make both the strings palindromic
int cntOp = 0;
while (i < j) {
// if str1[i] equal to str1[j]
// and str2[i] not equal to str2[j]
if (str1[i] == str1[j]
&& str2[i] != str2[j]) {
// Update cntOp
cntOp += 1;
}
// If str1[i] not equal to str1[j]
// and str2[i] equal to str2[j]
else if (str1[i] != str1[j]
&& str2[i] == str2[j]) {
// Update cntOp
cntOp += 1;
}
// If str1[i] is not equal to str1[j]
// and str2[i] is not equal to str2[j]
else if (str1[i] != str1[j]
&& str2[i] != str2[j]) {
// If str1[i] is equal to str2[j]
// and str2[i] is equal to str1[j]
if (str1[i] == str2[j]
&& str2[i] == str1[j]) {
// Update cntOp
cntOp += 1;
}
else {
// Update cntOp
cntOp += 2;
}
}
// Update i and j
i += 1;
j -= 1;
}
return cntOp;
}
// Driver Code
int main()
{
string str1 = "dbba";
string str2 = "abcd";
// Stores length of str1
int N = str1.length();
cout << MincntBothPalin(
str1, str2, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find minimum operations
// to make both the Strings palindromic
static int MincntBothPalin(char[] str1,
char[] str2, int N)
{
// Stores index of
// the left pointer
int i = 0;
// Stores index of
// the right pointer
int j = N - 1;
// Stores count of minimum operations to
// make both the Strings palindromic
int cntOp = 0;
while (i < j)
{
// If str1[i] equal to str1[j]
// and str2[i] not equal to str2[j]
if (str1[i] == str1[j] &&
str2[i] != str2[j])
{
// Update cntOp
cntOp += 1;
}
// If str1[i] not equal to str1[j]
// and str2[i] equal to str2[j]
else if (str1[i] != str1[j] &&
str2[i] == str2[j])
{
// Update cntOp
cntOp += 1;
}
// If str1[i] is not equal to str1[j]
// and str2[i] is not equal to str2[j]
else if (str1[i] != str1[j] &&
str2[i] != str2[j])
{
// If str1[i] is equal to str2[j]
// and str2[i] is equal to str1[j]
if (str1[i] == str2[j] &&
str2[i] == str1[j])
{
// Update cntOp
cntOp += 1;
}
else
{
// Update cntOp
cntOp += 2;
}
}
// Update i and j
i += 1;
j -= 1;
}
return cntOp;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "dbba";
String str2 = "abcd";
// Stores length of str1
int N = str1.length();
System.out.print(MincntBothPalin(
str1.toCharArray(), str2.toCharArray(), N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach # Function to find minimum # operations to make both # the strings palindromic def MincntBothPalin(str1, str2, N): # Stores index of # the left pointer i = 0 # Stores index of # the right pointer j = N - 1 # Stores count of minimum # operations to make both # the strings palindromic cntOp = 0 while (i < j): # if str1[i] equal to # str1[j] and str2[i] # not equal to str2[j] if (str1[i] == str1[j] and str2[i] != str2[j]): # Update cntOp cntOp += 1 # If str1[i] not equal # to str1[j] and str2[i] # equal to str2[j] elif (str1[i] != str1[j] and str2[i] == str2[j]): # Update cntOp cntOp += 1 # If str1[i] is not equal # to str1[j] and str2[i] # is not equal to str2[j] elif (str1[i] != str1[j] and str2[i] != str2[j]): # If str1[i] is equal to # str2[j] and str2[i] is # equal to str1[j] if (str1[i] == str2[j] and str2[i] == str1[j]): # Update cntOp cntOp += 1 else: # Update cntOp cntOp += 2 # Update i and j i += 1 j -= 1 return cntOp # Driver Code if __name__ == "__main__": str1 = "dbba" str2 = "abcd" # Stores length of str1 N = len(str1) print(MincntBothPalin(str1, str2, N)) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find minimum operations
// to make both the strings palindromic
static int MincntBothPalin(string str1,
string str2, int N)
{
// Stores index of
// the left pointer
int i = 0;
// Stores index of
// the right pointer
int j = N - 1;
// Stores count of minimum
// operations to make both
// the strings palindromic
int cntOp = 0;
while (i < j)
{
// If str1[i] equal to
// str1[j] and str2[i]
// not equal to str2[j]
if (str1[i] == str1[j] &&
str2[i] != str2[j])
{
// Update cntOp
cntOp += 1;
}
// If str1[i] not equal
// to str1[j] and str2[i]
// equal to str2[j]
else if (str1[i] != str1[j] &&
str2[i] == str2[j])
{
// Update cntOp
cntOp += 1;
}
// If str1[i] is not equal
// to str1[j] and str2[i]
// is not equal to str2[j]
else if (str1[i] != str1[j] &&
str2[i] != str2[j])
{
// If str1[i] is equal
// to str2[j] and str2[i]
// is equal to str1[j]
if (str1[i] == str2[j] &&
str2[i] == str1[j])
{
// Update cntOp
cntOp += 1;
}
else
{
// Update cntOp
cntOp += 2;
}
}
// Update i and j
i += 1;
j -= 1;
}
return cntOp;
}
// Driver Code
public static void Main()
{
string str1 = "dbba";
string str2 = "abcd";
// Stores length of str1
int N = str1.Length;
Console.WriteLine(
MincntBothPalin(str1,
str2, N));
}
}
// This code is contributed by bgangwar59
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find minimum operations
// to make both the strings palindromic
function MincntBothPalin(str1, str2, N)
{
// Stores index of
// the left pointer
var i = 0;
// Stores index of
// the right pointer
var j = N - 1;
// Stores count of minimum operations to
// make both the strings palindromic
var cntOp = 0;
while (i < j) {
// if str1[i] equal to str1[j]
// and str2[i] not equal to str2[j]
if (str1[i] === str1[j] &&
str2[i] !== str2[j]) {
// Update cntOp
cntOp += 1;
}
// If str1[i] not equal to str1[j]
// and str2[i] equal to str2[j]
else if (str1[i] !== str1[j] &&
str2[i] === str2[j]) {
// Update cntOp
cntOp += 1;
}
// If str1[i] is not equal to str1[j]
// and str2[i] is not equal to str2[j]
else if (str1[i] !== str1[j] &&
str2[i] !== str2[j])
{
// If str1[i] is equal to str2[j]
// and str2[i] is equal to str1[j]
if (str1[i] === str2[j] &&
str2[i] === str1[j]) {
// Update cntOp
cntOp += 1;
} else {
// Update cntOp
cntOp += 2;
}
}
// Update i and j
i += 1;
j -= 1;
}
return cntOp;
}
// Driver Code
var str1 = "dbba";
var str2 = "abcd";
// Stores length of str1
var N = str1.length;
document.write(MincntBothPalin(str1, str2, N));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA