Compruebe si dos strings binarias se pueden igualar intercambiando pares de caracteres desiguales

Dadas dos strings binarias S1 y S2 de longitud N ( 1 ≤ N ≤ 10 ⁵ ), la tarea es verificar si es posible convertir la string S1 a 
S2 realizando las siguientes operaciones cualquier número de veces:

1. Seleccione cualquiera de los dos índices i y j ( 1 ≤ i < j ≤ N ) de modo que S1[i] sea ‘0’ y S1[j] sea ‘1’ .
2. Cambia S1[i] por S1[j] .

Ejemplos:

Entrada: S1 =”100111″, S2 = “111010” 
Salida : SÍ 
Explicación: Intercambiar S[2] y S[3] con S[4] y S[6] respectivamente.

Entrada: S1 = “110100”, S2 = “010101” 
Salida: NO

Enfoque: siga los pasos a continuación para resolver el problema:

1. Compruebe si el número de apariciones de los caracteres ‘0’ y ‘1’ en ambas strings es igual. Si no se encuentra que sea cierto, entonces es imposible transformar la string S1 en S2 .
2. Si el número de caracteres es igual, pasamos al siguiente paso. Según la condición dada, es posible mover el ‘0’ solo hacia adelante intercambiando con la letra ‘1’ en la string S1 .
3. Por lo tanto, repita los caracteres de ambas strings y cuente el número de apariciones de ‘0’ en ambas strings. Si en algún momento el conteo de caracteres de ‘0’ en la string S2 se vuelve estrictamente mayor que el conteo de ocurrencias en la string S1 , termine el ciclo e imprima “NO” .
4. Si ambas strings iteraron con éxito, imprima «SÍ» .

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

// C++ Program to implement
// of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a string
// s1 can be converted into s2
void check(string s1, string s2)
{
    // Count of '0' in strings in s1 and s2
    int s1_0 = 0, s2_0 = 0;
 
    // Iterate both the strings and
    // count the number of occurrences of
    for (int i = 0; i < s1.size(); i++) {
 
        if (s1[i] == '0') {
            s1_0++;
        }
 
        if (s2[i] == '0') {
            s2_0++;
        }
    }
 
    // Count is not equal
    if (s1_0 != s2_0) {
        cout << "NO" << endl;
        return;
    }
 
    else {
 
        int Count1 = 0, Count2 = 0;
 
        // Iterating over both the
        // arrays and count the
        // number of occurrences of '0'
        for (int i = 0; i < s1.size(); i++) {
 
            if (s1[i] == '0') {
                Count1++;
            }
 
            if (s2[i] == '0') {
                Count2++;
            }
 
            // If the count of occurrences
            // of '0' in S2 exceeds that in S1
            if (Count1 < Count2) {
                cout << "NO" << endl;
                return;
            }
        }
 
        cout << "YES" << endl;
    }
}
 
// Driver program
int main()
{
 
    string s1 = "100111";
    string s2 = "111010";
    check(s1, s2);
 
    s1 = "110100";
    s2 = "010101";
    check(s1, s2);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
  
// Function to check if a string
// s1 can be converted into s2
static void check(String s1, String s2)
{
     
    // Count of '0' in strings in s1 and s2
    int s1_0 = 0, s2_0 = 0;
     
    // Iterate both the strings and
    // count the number of occurrences of
    for(int i = 0; i < s1.length(); i++)
    {
        if (s1.charAt(i) == '0')
        {
            s1_0++;
        }
   
        if (s2.charAt(i) == '0')
        {
            s2_0++;
        }
    }
   
    // Count is not equal
    if (s1_0 != s2_0)
    {
        System.out.println("NO");
        return;
    }
   
    else
    {
        int Count1 = 0, Count2 = 0;
         
        // Iterating over both the
        // arrays and count the
        // number of occurrences of '0'
        for(int i = 0; i < s1.length(); i++)
        {
            if (s1.charAt(i) == '0')
            {
                Count1++;
            }
   
            if (s2.charAt(i) == '0')
            {
                Count2++;
            }
   
            // If the count of occurrences
            // of '0' in S2 exceeds that in S1
            if (Count1 < Count2)
            {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}
  
// Driver Code
public static void main(String[] args)
{
    String s1 = "100111";
    String s2 = "111010";    
    check(s1, s2);
    s1 = "110100";
    s2 = "010101";
    check(s1, s2);
}
}
 
// This code is contributed by code_hunt.

# Python3 program to implement
# of above approach
 
# Function to check if a string
# s1 can be converted into s2
def check(s1, s2):
 
    # Count of '0' in strings in s1 and s2
    s1_0 = 0
    s2_0 = 0
 
    # Iterate both the strings and
    # count the number of occurrences of
    for i in range(len(s1)):
        if (s1[i] == '0'):
            s1_0 += 1
             
        if (s2[i] == '0'):
            s2_0 += 1
 
    # Count is not equal
    if (s1_0 != s2_0):
        print("NO")
        return
 
    else:
        Count1 = 0
        Count2 = 0;
 
        # Iterating over both the
        # arrays and count the
        # number of occurrences of '0'
        for i in range(len(s1)):
            if (s1[i] == '0'):
                Count1 += 1
 
            if (s2[i] == '0'):
                Count2 += 1
 
            # If the count of occurrences
            # of '0' in S2 exceeds that in S1
            if (Count1 < Count2):
                print("NO")
                return
            
        print("YES")
 
# Driver code
if __name__ == "__main__":
 
    s1 = "100111"
    s2 = "111010"
    check(s1, s2)
 
    s1 = "110100"
    s2 = "010101"
    check(s1, s2)
 
# This code is contributed by chitranayal

// C# program to implement
// of above approach
using System;
 
class GFG{
     
// Function to check if a string
// s1 can be converted into s2
static void check(string s1, string s2)
{
     
    // Count of '0' in strings in s1 and s2
    int s1_0 = 0, s2_0 = 0;
     
    // Iterate both the strings and
    // count the number of occurrences of
    for(int i = 0; i < s1.Length; i++)
    {
        if (s1[i] == '0')
        {
            s1_0++;
        }
   
        if (s2[i] == '0')
        {
            s2_0++;
        }
    }
   
    // Count is not equal
    if (s1_0 != s2_0)
    {
        Console.WriteLine("NO");
        return;
    }
   
    else
    {
        int Count1 = 0, Count2 = 0;
         
        // Iterating over both the
        // arrays and count the
        // number of occurrences of '0'
        for(int i = 0; i < s1.Length; i++)
        {
            if (s1[i] == '0')
            {
                Count1++;
            }
   
            if (s2[i] == '0')
            {
                Count2++;
            }
   
            // If the count of occurrences
            // of '0' in S2 exceeds that in S1
            if (Count1 < Count2)
            {
                Console.WriteLine("NO");
                return;
            }
        }
        Console.WriteLine("YES");
    }
}
 
// Driver code
static void Main()
{
    string s1 = "100111";
    string s2 = "111010";
     
    check(s1, s2);
     
    s1 = "110100";
    s2 = "010101";
     
    check(s1, s2);
}
}
 
// This code is contributed by divyesh072019

<script>
    // Javascript program to implement of above approach
     
    // Function to check if a string
    // s1 can be converted into s2
    function check(s1, s2)
    {
 
        // Count of '0' in strings in s1 and s2
        let s1_0 = 0, s2_0 = 0;
 
        // Iterate both the strings and
        // count the number of occurrences of
        for(let i = 0; i < s1.length; i++)
        {
            if (s1[i] == '0')
            {
                s1_0++;
            }
 
            if (s2[i] == '0')
            {
                s2_0++;
            }
        }
 
        // Count is not equal
        if (s1_0 != s2_0)
        {
            document.write("NO");
            return;
        }
 
        else
        {
            let Count1 = 0, Count2 = 0;
 
            // Iterating over both the
            // arrays and count the
            // number of occurrences of '0'
            for(let i = 0; i < s1.length; i++)
            {
                if (s1[i] == '0')
                {
                    Count1++;
                }
 
                if (s2[i] == '0')
                {
                    Count2++;
                }
 
                // If the count of occurrences
                // of '0' in S2 exceeds that in S1
                if (Count1 < Count2)
                {
                    document.write("NO" + "</br>");
                    return;
                }
            }
            document.write("YES" + "</br>");
        }
    }
     
    let s1 = "100111";
    let s2 = "111010";
      
    check(s1, s2);
      
    s1 = "110100";
    s2 = "010101";
      
    check(s1, s2);
   
  // This code is contributed by decode 2207.
</script>

YES
NO

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