Número mínimo de cambios o intercambios de caracteres adyacentes requeridos para hacer que dos strings sean iguales

Dadas dos strings binarias A y B de longitud N , la tarea es contar el número mínimo de operaciones requeridas para igualar las dos strings dadas intercambiando caracteres adyacentes o invirtiendo cualquier carácter de la string A .

Ejemplos:

Entrada: A = “100”, B = “001”
Salida: 2
Explicación: Cambiar los caracteres A[0](= ‘1’) y A[2](= ‘0’) modifica la string A a “001”, que es igual a la string B.

Entrada: A = “0101”, B = “0011”
Salida: 1
Explicación: Al intercambiar los caracteres A[2](= ‘0’) y A[3](= ‘1’) se modifica la string A a “0011” , que es igual a la string B.

Enfoque: el problema se puede resolver utilizando la programación dinámica , ya que tiene subproblemas superpuestos y una subestructura óptima . 
Siga los pasos a continuación para resolver el problema:

• Inicialice una array , digamos dp[] de tamaño N+1 como {0} , donde dp[i] almacena la cantidad mínima de operaciones requeridas hasta el índice i, para hacer que el prefijo de A _i sea igual al prefijo B _i .
• Iterar sobre el rango [1, N] usando una variable, digamos i , y realizando las siguientes operaciones:
  • Si A[i – 1] es igual a B[i – 1], actualice dp[i] a dp[i – 1] .
  • De lo contrario, actualice dp[i] a dp[i – 1] + 1 .
  • Si el intercambio es posible, es decir, i > 1 y A[i – 2] es igual a B[i – 1] y A[i – 1] es igual a B[i – 2], entonces actualice dp[i] a min (dp[i], dp[i – 2] + 1).
• Después de completar los pasos anteriores, imprima el número mínimo de operaciones obtenidas, es decir, el valor dp[N].

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 count the minimum
// number of operations required
// to make strings A and B equal
int countMinSteps(string A, string B, int N)
{
 
    // Stores all dp-states
    vector<int> dp(N + 1, 0);
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // If A[i - 1] equals to B[i - 1]
        if (A[i - 1] == B[i - 1]) {
 
            // Assign Dp[i - 1] to Dp[i]
            dp[i] = dp[i - 1];
        }
 
        // Otherwise
        else {
 
            // Update dp[i]
            dp[i] = dp[i - 1] + 1;
        }
 
        // If swapping is possible
        if (i >= 2 && A[i - 2] == B[i - 1]
            && A[i - 1] == B[i - 2]) {
 
            // Update dp[i]
            dp[i] = min(dp[i], dp[i - 2] + 1);
        }
    }
 
    // Return the minimum
    // number of steps required
    return dp[N];
}
 
// Driver Code
int main()
{
    // Given Input
    string A = "0101";
    string B = "0011";
    int N = A.length();
 
    // Function Call
    cout << countMinSteps(A, B, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to count the minimum
// number of operations required
// to make strings A and B equal
static int countMinSteps(String A, String B, int N)
{
     
    // Stores all dp-states
    int[] dp = new int[N + 1];
    for(int i = 1; i <= N; i++)
    {
         
        // Update the value of A[i]
        dp[i] = 0;
    }
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // If A[i - 1] equals to B[i - 1]
        if (A.charAt(i - 1) == B.charAt(i - 1))
        {
             
            // Assign Dp[i - 1] to Dp[i]
            dp[i] = dp[i - 1];
        }
 
        // Otherwise
        else
        {
             
            // Update dp[i]
            dp[i] = dp[i - 1] + 1;
        }
 
        // If swapping is possible
        if (i >= 2 && A.charAt(i - 2) == B.charAt(i - 1) &&
                      A.charAt(i - 1) == B.charAt(i - 2))
        {
             
            // Update dp[i]
            dp[i] = Math.min(dp[i], dp[i - 2] + 1);
        }
    }
 
    // Return the minimum
    // number of steps required
    return dp[N];
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Input
    String A = "0101";
    String B = "0011";
    int N = A.length();
     
    // Function Call
    System.out.println(countMinSteps(A, B, N));
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
 
# Function to count the minimum
# number of operations required
# to make strings A and B equal
def countMinSteps(A, B, N) :
 
    # Stores all dp-states
    dp = [0] * (N + 1)
 
    # Iterate rate over the range [1, N]
    for i in range(1, N+1) :
 
        # If A[i - 1] equals to B[i - 1]
        if (A[i - 1] == B[i - 1]) :
 
            # Assign Dp[i - 1] to Dp[i]
            dp[i] = dp[i - 1]
         
 
        # Otherwise
        else :
 
            # Update dp[i]
            dp[i] = dp[i - 1] + 1
         
 
        # If swapping is possible
        if (i >= 2 and A[i - 2] == B[i - 1]
            and A[i - 1] == B[i - 2]) :
 
            # Update dp[i]
            dp[i] = min(dp[i], dp[i - 2] + 1)
         
    # Return the minimum
    # number of steps required
    return dp[N]
 
 
# Driver Code
 
# Given Input
A = "0101"
B = "0011"
N = len(A)
 
# Function Call
print(countMinSteps(A, B, N))
 
# This code is contributed by splevel62.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the minimum
// number of operations required
// to make strings A and B equal
static int countMinSteps(string A, string B, int N)
{
     
    // Stores all dp-states
    int[] dp = new int[N + 1];
    for(int i = 1; i <= N; i++)
    {
         
        // Update the value of A[i]
        dp[i] = 0;
    }
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // If A[i - 1] equals to B[i - 1]
        if (A[i - 1] == B[i - 1])
        {
             
            // Assign Dp[i - 1] to Dp[i]
            dp[i] = dp[i - 1];
        }
 
        // Otherwise
        else
        {
             
            // Update dp[i]
            dp[i] = dp[i - 1] + 1;
        }
 
        // If swapping is possible
        if (i >= 2 && A[i - 2] == B[i - 1] &&
                      A[i - 1] == B[i - 2])
        {
             
            // Update dp[i]
            dp[i] = Math.Min(dp[i], dp[i - 2] + 1);
        }
    }
 
    // Return the minimum
    // number of steps required
    return dp[N];
}
 
// Driver code
public static void Main(String []args)
{
     
    // Given Input
    string A = "0101";
    string B = "0011";
    int N = A.Length;
 
    // Function Call
    Console.Write(countMinSteps(A, B, N));
}
}
 
// This code is contributed by code_hunt

<script>
       // JavaScript Program for the above approach
 
 
       // Function to count the minimum
       // number of operations required
       // to make strings A and B equal
       function countMinSteps(A, B, N) {
 
           // Stores all dp-states
           let dp = new Array(N + 1).fill(0);
 
           // Iterate over the range [1, N]
           for (let i = 1; i <= N; i++) {
 
               // If A[i - 1] equals to B[i - 1]
               if (A[i - 1] == B[i - 1]) {
 
                   // Assign Dp[i - 1] to Dp[i]
                   dp[i] = dp[i - 1];
               }
 
               // Otherwise
               else {
 
                   // Update dp[i]
                   dp[i] = dp[i - 1] + 1;
               }
 
               // If swapping is possible
               if (i >= 2 && A[i - 2] == B[i - 1]
                   && A[i - 1] == B[i - 2]) {
 
                   // Update dp[i]
                   dp[i] = Math.min(dp[i], dp[i - 2] + 1);
               }
           }
 
           // Return the minimum
           // number of steps required
           return dp[N];
       }
 
       // Driver Code
 
       // Given Input
       let A = "0101";
       let B = "0011";
       let N = A.length;
 
       // Function Call
       document.write(countMinSteps(A, B, N));
 
 
   // This code is contributed by Potta Lokesh
   </script>

1

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