Cambios mínimos o intercambio de caracteres adyacentes necesarios para hacer que una string sea igual a otra

Dadas dos strings binarias A y B de longitud N , la tarea es convertir la string A en B cambiando cualquier carácter de A o intercambiando caracteres adyacentes de A un número mínimo de veces. Si no es posible hacer que ambas strings sean iguales, imprima -1 .

Ejemplos:

Entrada: A = “10010010”, B = “00001000”  
Salida: 3
Explicación:
Operación 1: Voltear A[0] modifica A a “00010010”.
Operación 2: Voltear A[6] modifica A a “00010000”.
Operación 3: Intercambiar A[3] y A[4] modifica A a “00001000” 
Por lo tanto, el número total de operaciones es 3.

Entrada: A = “11”, B = “00”  
Salida: 3

Enfoque: la idea es atravesar la string A e intentar que los mismos caracteres indexados sean iguales comprobando primero la condición de intercambiar los caracteres adyacentes. Si los caracteres no pueden igualarse mediante esta operación, invierta el carácter. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans, para almacenar el resultado requerido.
• Recorra la string A usando una variable, digamos i , y realice las siguientes operaciones:
  • Si A[i] es igual a B[i], continúe con la siguiente iteración en el bucle .
  • De lo contrario, si A[i] es igual a B[i + 1] y A[i + 1] es igual a B[i] , entonces intercambie los caracteres e incremente i y ans en 1 .
  • De lo contrario, si A[i] no es igual a B[i] , cambie el bit actual e incremente ans en 1 .
• Imprime el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations
// required to convert string A to B
int minimumOperation(string a, string b)
{
 
    // Store the size of the string
    int n = a.length();
    int i = 0;
 
    // Store the required result
    int minoperation = 0;
 
    // Traverse the string, a
    while (i < n) {
 
        // If a[i] is equal to b[i]
        if (a[i] == b[i]) {
            i = i + 1;
            continue;
        }
 
        // Check if swapping adjacent
        // characters make the same-indexed
        // characters equal or not
        else if (a[i] == b[i + 1]
                 && a[i + 1] == b[i]
                 && i < n - 1) {
 
            minoperation++;
            i = i + 2;
        }
 
        // Otherwise, flip the current bit
        else if (a[i] != b[i]) {
            minoperation++;
            i = i + 1;
        }
        else {
            ++i;
        }
    }
 
    // Print the minimum number of operations
    cout << minoperation;
}
 
// Driver Code
int main()
{
    // Given Input
    string a = "10010010", b = "00001000";
 
    // Function Call
    minimumOperation(a, b);
 
    return 0;
}

// Java program for the above approach
public class GFG
{
     
// Function to find minimum operations
// required to convert string A to B
static void minimumOperation(String a, String b)
{
     
    // Store the size of the string
    int n = a.length();
    int i = 0;
 
    // Store the required result
    int minoperation = 0;
 
    // Traverse the string, a
    while (i < n)
    {
         
        // If a[i] is equal to b[i]
        if (a.charAt(i) == b.charAt(i))
        {
            i = i + 1;
            continue;
        }
 
        // Check if swapping adjacent
        // characters make the same-indexed
        // characters equal or not
        else if (a.charAt(i) == b.charAt(i + 1) && 
                 a.charAt(i + 1) == b.charAt(i) &&
                   i < n - 1)
        {
            minoperation++;
            i = i + 2;
        }
 
        // Otherwise, flip the current bit
        else if (a.charAt(i) != b.charAt(i))
        {
            minoperation++;
            i = i + 1;
        }
        else
        {
            ++i;
        }
    }
 
    // Print the minimum number of operations
    System.out.println(minoperation);
}
 
// Driver Code
public static void main(String []args)
{
     
    // Given Input
    String a = "10010010", b = "00001000";
 
    // Function Call
    minimumOperation(a, b);
}
}
 
// This code is contributed by AnkThon

# Python3 program for the above approach
 
# Function to find minimum operations
# required to convert A to B
def minimumOperation(a, b):
 
    # Store the size of the string
    n = len(a)
    i = 0
 
    # Store the required result
    minoperation = 0
 
    # Traverse the string, a
    while (i < n):
 
        # If a[i] is equal to b[i]
        if (a[i] == b[i]):
            i = i + 1
            continue
 
        # Check if swapping adjacent
        # characters make the same-indexed
        # characters equal or not
        elif (a[i] == b[i + 1] and
              a[i + 1] == b[i] and i < n - 1):
            minoperation += 1
            i = i + 2
 
        # Otherwise, flip the current bit
        elif (a[i] != b[i]):
            minoperation += 1
            i = i + 1
        else:
            i+=1
 
    # Print the minimum number of operations
    print (minoperation)
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    a = "10010010"
    b = "00001000"
 
    # Function Call
    minimumOperation(a, b)
     
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find minimum operations
// required to convert string A to B
static void minimumOperation(string a, string b)
{
     
    // Store the size of the string
    int n = a.Length;
    int i = 0;
 
    // Store the required result
    int minoperation = 0;
 
    // Traverse the string, a
    while (i < n)
    {
         
        // If a[i] is equal to b[i]
        if (a[i] == b[i])
        {
            i = i + 1;
            continue;
        }
 
        // Check if swapping adjacent
        // characters make the same-indexed
        // characters equal or not
        else if (a[i] == b[i + 1] && 
                 a[i + 1] == b[i] &&
                   i < n - 1)
        {
            minoperation++;
            i = i + 2;
        }
 
        // Otherwise, flip the current bit
        else if (a[i] != b[i])
        {
            minoperation++;
            i = i + 1;
        }
        else
        {
            ++i;
        }
    }
 
    // Print the minimum number of operations
    Console.WriteLine(minoperation);
}
 
// Driver Code
public static void Main()
{
     
    // Given Input
    string a = "10010010", b = "00001000";
 
    // Function Call
    minimumOperation(a, b);
}
}
 
// This code is contributed by ankThon

<script>
 
// Javascript program for the above approach
 
// Function to find minimum operations
// required to convert string A to B
function minimumOperation(a, b)
{
 
    // Store the size of the string
    var n = a.length;
    var i = 0;
 
    // Store the required result
    var minoperation = 0;
 
    // Traverse the string, a
    while (i < n) {
 
        // If a[i] is equal to b[i]
        if (a[i] == b[i]) {
            i = i + 1;
            continue;
        }
 
        // Check if swapping adjacent
        // characters make the same-indexed
        // characters equal or not
        else if (a[i] == b[i + 1]
                 && a[i + 1] == b[i]
                 && i < n - 1) {
 
            minoperation++;
            i = i + 2;
        }
 
        // Otherwise, flip the current bit
        else if (a[i] != b[i]) {
            minoperation++;
            i = i + 1;
        }
        else {
            ++i;
        }
    }
 
    // Print the minimum number of operations
    document.write(minoperation);
}
 
// Driver Code
 
    // Given Input
    var a = "10010010", b = "00001000";
 
    // Function Call
    minimumOperation(a, b);
     
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar:  O(1)