Compruebe si dos strings binarias se pueden hacer iguales haciendo XOR bit a bit de adyacentes

Dadas las strings binarias S1 y S2 de longitud N , la tarea es verificar si S2 puede hacerse igual a S1 realizando las siguientes operaciones en S2:

• La primera operación es S _i = S _i ⊕ S _i+1. ( ⊕ es la operación XOR)
• La segunda operación es S _i+1 = S _i+1 ⊕ S _i.

Ejemplos:

Entrada: S1 = “00100”, S2 = “00011” 
Salida: Sí 

Explicación: Podemos aplicar las siguientes operaciones en S2:
1. Seleccione i = 2, por lo que la conversión es 00 01 1 → 00 11 1 
2. Seleccione i = 3. Entonces la conversión es 001 11 → 001 00 .
Por lo tanto, es posible hacer que S2 sea igual a S1 aplicando la operación anterior en el índice 2 y 3.

Entrada: S1 = “10101”, S2 = “01000” 

Salida: No

Planteamiento: El problema se puede resolver con base en la siguiente observación: 

Las operaciones tienen los siguientes efectos:

1. 01 se convierte en 11
2. 10 se convierte en 11
3. 00 se convierte en 00
4. 11 se convierte en 00

Dejemos los casos fáciles fuera del camino:

• Si S2 = S1, la respuesta es SI
• Si S2 es 000…00 (es decir, S2 no tiene 1), entonces solo podemos realizar la operación y será el tercer caso que se muestra arriba, que no cambia nada. Por tanto, la respuesta es NO si S2 ≠ S1.
• Ahora, suponga que S2 ≠ S1 y S2 tiene un 1 . Es posible convertir S2 a S1 si y solo si S1 tiene al menos dos caracteres idénticos consecutivos.

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Compruebe si las strings ya son iguales entre sí. Si es así, devuelve verdadero.
• De lo contrario, verifique si S2 tiene al menos un ‘1’ :
  • Si es así, verifique la condición de que S1 tenga al menos dos caracteres idénticos consecutivos.
  • Si se cumple la condición anterior, devuelve verdadero.
  • De lo contrario, devuelve falso.

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

// Java code to implement the approach
  
import java.io.*;
import java.util.*;
  
class GFG {
  
    // Function to check whether S2 can be made equal
    // to S1 after performing given operations
    public static void checkEqual(String S1,
                                  String S2, int n)
    {
        char[] a = S2.toCharArray();
        char[] b = S1.toCharArray();
  
        int c_1 = 0;
        int c_2 = 0;
        if (String.valueOf(a).equals(String.valueOf(b))) {
            System.out.println("Yes");
        }
        for (int j = 0; j < n; j++) {
            if (a[j] == '1') {
                c_1++;
            }
            if (b[j] == '1') {
                c_2++;
            }
        }
        if (c_1 == 0 && c_2 > 0) {
            System.out.println("No");
        }
        int c = 0;
        for (int k = 0; k < n - 1; k++) {
            if (b[k] != b[k + 1]) {
                c++;
            }
        }
        if (c == n - 1) {
            System.out.println("No");
        }
        else {
            System.out.println("Yes");
        }
    }
  
    // Driver code
    public static void main(String[] args)
    {
        String S1 = "00100";
        String S2 = "00011";
        int N = S1.length();
  
        // Function call
        checkEqual(S1, S2, N);
    }
}

Yes

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