Given two strings str1 and str2 of size N consisting of only three characters A, B, and C, the task is to check whether the string str1 can be changed to str2 using the below operations:
- Replacing one occurrence of “BC” with “CB” i.e swap adjacent ‘B’ and ‘C’.
- Replacing one occurrence of “CA” with “AC” i.e swap adjacent ‘C’ and ‘A’.
Print “Yes” if we can transform the string else print “No”.
Examples:
Input: str1 = “BCCABCBCA”, str2 = “CBACCBBAC”
Output: Yes
Explanation:
Transform the strings using following these steps:
BCCABCBCA -> CBCABCBCA -> CBACBCBCA -> CBACCBBCA -> CBACCBBAC.
Input: str1 = “BAC”, str2 = “CAB”
Output: False
Naive Approach: The idea is to generate all possible strings recursively from the start of the string str1 by performing the given operations and store it in a set of strings. Then check if any string from the set is equal to the string str2 or not. If string str2 is found in the set then print “Yes” else print “No”.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to transverse the two strings simultaneously and check if it’s possible to transform the string str1 to str2 till a particular index. Below are the steps:
- Check for the sequence ‘A’ and ‘B’ in the strings str1 and str2, if it’s the same, then proceed to the second step. Otherwise, print “No” as the desired conversion is not possible.
- The index of ‘A’ in str1 should be greater than and equal to the index of the corresponding ‘A’ in str2, since “CA” can be converted only to “AC”.
- Similarly, the index of ‘B’ in str1 string should be less than or equal to the corresponding index of ‘B’ in str2, since “BC” can only be converted to “CB”.
- If the above two conditions are not satisfied, then print “No”. Otherwise, print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to transform start to endbool 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 Codeint main(){ string str1 = "BCCABCBCA"; string str2 = "CBACCBBAC"; // Function Call if (canTransform(str1, str2)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java program for the above approachimport 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
# Python3 program for the above approach# Function to check if it is possible# to transform start to enddef 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 Codeif __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#
// C# program for the above approachusing System;class GFG{// Function to check if it is possible// to transform start to endstatic 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 Codepublic 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 |
Javascript
<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> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
