Número mínimo de intercambios para hacer que dos strings binarias sean iguales

Dadas dos strings binarias de igual longitud, la tarea es encontrar el número mínimo de intercambios para que sean iguales. Solo se permite intercambiar entre dos caracteres de dos strings diferentes, devuelve -1 si las strings no se pueden igualar.

Ejemplos:

Input: s1 = "0011", s2 = "1111" 
Output: 1
Explanation:
Swap s1[0] and s2[1].After swap
s1 = 1011 and s2 = 1011 

Input: s1 = "00011", s2 = "01001"
Output: 2
Swap s1[1] and s2[1]. After swap
s1 = 01011, s2 = 00001 
Swap s1[3] and s2[1]. After swap,
s1 = 01001, s2 = 01001

Acercarse:

Se puede encontrar la siguiente observación:
• Se permite el intercambio de s1[i] y s2[j], por lo que debemos encontrar en qué posiciones son diferentes dos strings. Si s1[i] y s2[i] son ​​iguales, no los intercambiamos.
• Si s1[i] y s2[i] no son iguales entonces podemos encontrar 3 patrones:
  1. 00 y 11, podemos realizar un intercambio diagonal y el resultado será 01 01 o 10 10. En el caso del intercambio diagonal, necesitamos formar parejas para resolver la desproporción de este tipo. El intercambio requerido para restaurar un solo par es 1.
  2. 11 y 00, podemos realizar un intercambio diagonal y el resultado será 01 01 o 10 10. En el caso del intercambio diagonal, necesitamos formar parejas para resolver la desproporción de este tipo. El intercambio requerido para restaurar un solo par es 1.
  3. 10 y 01, podemos realizar un intercambio vertical y el resultado será 00 11 o 11 00 y este tipo se transformará en un problema de tipo 1 o tipo 2 y otro intercambio diagonal para igualarlos. necesitamos formar pareja para resolver desproporción de este tipo. El intercambio requerido para restaurar un solo par es 2.
• De la observación anterior, podemos seguir el siguiente método codicioso:
  1. Cuente las posiciones donde s1[i] = 0 y s2[i] = 1 (count0). Necesitamos (count0)/2 número de intercambios diagonales en cada par de tipo 1.
  2. Cuente las posiciones donde s1[i] =1 y s2[i] = 0 (cuenta1). Necesitamos (count1)/2 número de intercambios diagonales en cada par de tipo 2.
  3. Si tanto count0 como count1 son pares, podemos generar la respuesta = ((count0) + (count1))/2. Si count0 y count1 son impares, podemos tener un solo par de desproporción de tipo 3, por lo que necesitamos 2 intercambios adicionales. Muestra la respuesta como ((count0) + (count1))/2 + 2. Si uno de count0 y count1 es impar, no podemos hacer que dos strings sean iguales. Como en todos los casos necesitamos formar pares, el conteo impar significa que una sola posición se quedará sola haciendo 2 strings desiguales.

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 calculate
// min swaps to make
// binary strings equal
int minSwaps(string& s1, string& s2)
{
  
    int c0 = 0, c1 = 0;
  
    for (int i = 0; i < s1.size(); i++) {
        // Count of zero's
        if (s1[i] == '0' && s2[i] == '1') {
            c0++;
        }
        // Count of one's
        else if (s1[i] == '1' && s2[i] == '0') {
            c1++;
        }
    }
  
    // As discussed
    // above
    int ans = c0 / 2 + c1 / 2;
  
    if (c0 % 2 == 0 && c1 % 2 == 0) {
        return ans;
    }
    else if ((c0 + c1) % 2 == 0) {
        return ans + 2;
    }
    else {
        return -1;
    }
}
  
// Driver code
int main()
{
  
    string s1 = "0011", s2 = "1111";
    int ans = minSwaps(s1, s2);
  
    cout << ans << '\n';
  
    return 0;
}

// Java program for the above approach 
  
class GFG 
{
  
    // Function to calculate 
    // min swaps to make 
    // binary strings equal 
    static int minSwaps(String s1, String s2) 
    { 
      
        int c0 = 0, c1 = 0; 
      
        for (int i = 0; i < s1.length(); i++)
        { 
            // Count of zero's 
            if (s1.charAt(i) == '0' && s2.charAt(i) == '1')
            { 
                c0++; 
            }
              
            // Count of one's 
            else if (s1.charAt(i) == '1' && s2.charAt(i) == '0')
            { 
                c1++; 
            } 
        } 
      
        // As discussed 
        // above 
        int ans = c0 / 2 + c1 / 2; 
      
        if (c0 % 2 == 0 && c1 % 2 == 0)
        { 
            return ans; 
        } 
        else if ((c0 + c1) % 2 == 0) 
        { 
            return ans + 2; 
        } 
        else
        { 
            return -1; 
        } 
    } 
      
    // Driver code 
    public static void main (String[] args)
    { 
      
        String s1 = "0011", s2 = "1111"; 
        int ans = minSwaps(s1, s2); 
      
        System.out.println(ans); 
      
    } 
  
}
  
// This code is contributed by AnkitRai01

# Python3 program for 
# the above approach 
  
# Function to calculate 
# min swaps to make 
# binary strings equal 
def minSwaps(s1, s2) : 
  
    c0 = 0; c1 = 0; 
  
    for i in range(len(s1)) :
          
        # Count of zero's 
        if (s1[i] == '0' and s2[i] == '1') :
            c0 += 1; 
      
        # Count of one's 
        elif (s1[i] == '1' and s2[i] == '0') :
            c1 += 1; 
  
    # As discussed above 
    ans = c0 // 2 + c1 // 2; 
  
    if (c0 % 2 == 0 and c1 % 2 == 0) :
        return ans; 
      
    elif ((c0 + c1) % 2 == 0) :
        return ans + 2; 
  
    else :
        return -1; 
  
# Driver code 
if __name__ == "__main__" : 
  
    s1 = "0011"; s2 = "1111"; 
      
    ans = minSwaps(s1, s2); 
  
    print(ans); 
  
# This code is contributed by AnkitRai01

// C# program for the above approach 
using System;
  
class GFG 
{
  
    // Function to calculate 
    // min swaps to make 
    // binary strings equal 
    static int minSwaps(string s1, string s2) 
    { 
      
        int c0 = 0, c1 = 0; 
      
        for (int i = 0; i < s1.Length; i++)
        { 
            // Count of zero's 
            if (s1[i] == '0' && s2[i] == '1')
            { 
                c0++; 
            }
              
            // Count of one's 
            else if (s1[i] == '1' && s2[i] == '0')
            { 
                c1++; 
            } 
        } 
      
        // As discussed 
        // above 
        int ans = c0 / 2 + c1 / 2; 
      
        if (c0 % 2 == 0 && c1 % 2 == 0)
        { 
            return ans; 
        } 
        else if ((c0 + c1) % 2 == 0) 
        { 
            return ans + 2; 
        } 
        else
        { 
            return -1; 
        } 
    } 
      
    // Driver code 
    public static void Main ()
    { 
      
        string s1 = "0011", s2 = "1111"; 
        int ans = minSwaps(s1, s2); 
      
        Console.WriteLine(ans); 
      
    } 
  
}
  
// This code is contributed by AnkitRai01

1

Complejidad de tiempo: O(n)