Compruebe si una string se puede convertir en otra mediante el intercambio de caracteres adyacentes de un tipo dado

Dadas dos strings str1 y str2 de tamaño N que consisten en solo tres caracteres A , B y C , la tarea es verificar si la string str1 se puede cambiar a str2 usando las siguientes operaciones:

• Reemplazar una aparición de «BC» con «CB», es decir, intercambiar ‘B’ y ‘C’ adyacentes.
• Reemplazar una aparición de «CA» con «AC», es decir, intercambiar ‘C’ y ‘A’ adyacentes.

Imprima » Sí» si podemos transformar la string, de lo contrario, imprima » No» .
Ejemplos:

Entrada: str1 = “BCCABCBCA”, str2 = “CBACCBBAC” 
Salida: Sí 
Explicación: 
Transforme las strings siguiendo estos pasos: 
BCCABCBCA -> CBCABCBCA -> CBACBCBCA -> CBACCBBCA -> CBACCBBAC.
Entrada: str1 = «BAC», str2 = «CAB» 
Salida: Falso

Enfoque ingenuo: la idea es generar todas las strings posibles de forma recursiva desde el comienzo de la string str1 realizando las operaciones dadas y almacenándolas en un conjunto de strings. Luego verifique si alguna string del conjunto es igual a la string str2 o no. Si se encuentra la string str2 en el conjunto, imprima » Sí»; de lo contrario, imprima » No» .

Complejidad de Tiempo: O(2 ^N ) 
Espacio Auxiliar: O(1)
Enfoque Eficiente: La idea es atravesar las dos strings simultáneamente y verificar si es posible transformar la string str1 a str2 hasta un índice particular. A continuación se muestran los pasos:

1. Verifique la secuencia ‘A’ y ‘B’ en las strings str1 y str2 , si es la misma, luego continúe con el segundo paso. De lo contrario, escriba “No” ya que la conversión deseada no es posible.
2. El índice de ‘A’ en str1 debe ser mayor e igual que el índice de la correspondiente ‘A’ en str2 , ya que «CA» solo se puede convertir en «AC».
3. De manera similar, el índice de ‘B’ en la string str1 debe ser menor o igual que el índice correspondiente de ‘B’ en str2 , ya que «BC» solo se puede convertir a «CB».
4. Si no se cumplen las dos condiciones anteriores, imprima “ No” . De lo contrario, escriba “ Sí” .

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 check if it is possible
// to transform start to end
bool canTransform(string str1,
                string str2)
{
    string s1 = "";
    string s2 = "";
 
    // Check the sequence of A, B in
    // both strings str1 and str2
    for (char c : str1) {
        if (c != 'C') {
            s1 += c;
        }
    }
 
    for (char c : str2) {
        if (c != 'C') {
            s2 += c;
        }
    }
 
    // If both the strings
    // are not equal
    if (s1 != s2)
        return false;
 
    int i = 0;
    int j = 0;
    int n = str1.length();
 
    // Traverse the strings
    while (i < n and j < n) {
        if (str1[i] == 'C') {
            i++;
        }
 
        else if (str2[j] == 'C') {
            j++;
        }
 
        // Check for indexes of A and B
        else {
            if ((str1[i] == 'A'
                and i < j)
                or (str1[i] == 'B'
                    and i > j)) {
                return false;
            }
            i++;
            j++;
        }
    }
 
    return true;
}
 
// Driver Code
int main()
{
    string str1 = "BCCABCBCA";
    string str2 = "CBACCBBAC";
 
    // Function Call
    if (canTransform(str1, str2)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
    // Function to check if it is possible
    // to transform start to end
    static boolean canTransform(String str1, String str2)
    {
        String s1 = "";
        String s2 = "";
 
        // Check the sequence of A, B in
        // both Strings str1 and str2
        for (char c : str1.toCharArray())
        {
            if (c != 'C')
            {
                s1 += c;
            }
        }
 
        for (char c : str2.toCharArray())
        {
            if (c != 'C')
            {
                s2 += c;
            }
        }
 
        // If both the Strings
        // are not equal
        if (!s1.equals(s2))
            return false;
 
        int i = 0;
        int j = 0;
        int n = str1.length();
 
        // Traverse the Strings
        while (i < n && j < n)
        {
            if (str1.charAt(i) == 'C')
            {
                i++;
            }
            else if (str2.charAt(j) == 'C')
            {
                j++;
            }
 
            // Check for indexes of A and B
            else
            {
                if ((str1.charAt(i) == 'A' && i < j) ||
                    (str1.charAt(i) == 'B' && i > j))
                {
                    return false;
                }
                i++;
                j++;
            }
        }
        return true;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String str1 = "BCCABCBCA";
        String str2 = "CBACCBBAC";
 
        // Function Call
        if (canTransform(str1, str2))
        {
            System.out.print("Yes");
        }
        else
        {
            System.out.print("No");
        }
    }
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to check if it is possible
# to transform start to end
def canTransform(str1, str2):
     
    s1 = ""
    s2 = ""
 
    # Check the sequence of A, B in
    # both strings str1 and str2
    for c in str1:
        if (c != 'C'):
            s1 += c
 
    for c in str2:
        if (c != 'C'):
            s2 += c
 
    # If both the strings
    # are not equal
    if (s1 != s2):
        return False
 
    i = 0
    j = 0
    n = len(str1)
 
    # Traverse the strings
    while (i < n and j < n):
        if (str1[i] == 'C'):
            i += 1
 
        elif (str2[j] == 'C'):
            j += 1
 
        # Check for indexes of A and B
        else:
            if ((str1[i] == 'A' and i < j) or
                (str1[i] == 'B' and i > j)):
                return False
                 
            i += 1
            j += 1
 
    return True
 
# Driver Code
if __name__ == '__main__':
     
    str1 = "BCCABCBCA"
    str2 = "CBACCBBAC"
 
    # Function call
    if (canTransform(str1, str2)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if it is possible
// to transform start to end
static bool canTransform(string str1, string str2)
{
    string s1 = "";
    string s2 = "";
 
    // Check the sequence of A, B in
    // both Strings str1 and str2
    foreach(char c in str1.ToCharArray())
    {
        if (c != 'C')
        {
            s1 += c;
        }
    }
 
    foreach(char c in str2.ToCharArray())
    {
        if (c != 'C')
        {
            s2 += c;
        }
    }
 
    // If both the Strings
    // are not equal
    if (s1 != s2)
        return false;
 
    int i = 0;
    int j = 0;
    int n = str1.Length;
 
    // Traverse the Strings
    while (i < n && j < n)
    {
        if (str1[i] == 'C')
        {
            i++;
        }
        else if (str2[j] == 'C')
        {
            j++;
        }
 
        // Check for indexes of A and B
        else
        {
            if ((str1[i] == 'A' && i < j) ||
                (str1[i] == 'B' && i > j))
            {
                return false;
            }
            i++;
            j++;
        }
    }
    return true;
}
 
// Driver Code
public static void Main(string[] args)
{
    string str1 = "BCCABCBCA";
    string str2 = "CBACCBBAC";
 
    // Function call
    if (canTransform(str1, str2))
    {
        Console.Write("Yes");
    }
    else
    {
        Console.Write("No");
    }
}
}
 
// This code is contributed by rutvik_56

<script>
      // JavaScript program for the above approach
      // Function to check if it is possible
      // to transform start to end
      function canTransform(str1, str2) {
        var s1 = "";
        var s2 = "";
 
        // Check the sequence of A, B in
        // both Strings str1 and str2
        for (const c of str1) {
          if (c !== "C") {
            s1 += c;
          }
        }
 
        for (const c of str2) {
          if (c !== "C") {
            s2 += c;
          }
        }
 
        // If both the Strings
        // are not equal
        if (s1 !== s2) return false;
 
        var i = 0;
        var j = 0;
        var n = str1.length;
 
        // Traverse the Strings
        while (i < n && j < n) {
          if (str1[i] === "C") {
            i++;
          } else if (str2[j] === "C") {
            j++;
          }
 
          // Check for indexes of A and B
          else {
            if ((str1[i] === "A" && i < j) || (str1[i] === "B" && i > j)) {
              return false;
            }
            i++;
            j++;
          }
        }
        return true;
      }
 
      // Driver Code
      var str1 = "BCCABCBCA";
      var str2 = "CBACCBBAC";
 
      // Function call
      if (canTransform(str1.split(""), str2.split(""))) {
        document.write("Yes");
      } else {
        document.write("No");
      }
    </script>

Yes

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