Make Binary Strings equal by replacing 2nd bit repeatedly
Given two binary strings S and T of size N and M respectively, the task is to check if S can be converted into T by doing the following operations, any number of times:
- Suppose a is the first character of S and b is the second character of S.
- Change the second character of S to either min(a, b) or max(a, b),
- and remove the first character.
- Note that the length of the string reduces by 1 after each operation.
Examples:
Input: S = β001001β , T = β11β
Output: YES
Explanation: Just do the max operation (change second character of S to max(first character, second character) and remove the first character 4 times on the string S.
- β001001β³ -> β01001β³
- β01001β³ -> β1001β³
- β1001β³ -> β101β³
- β101β³ -> β11β³ , which is equal to the string T
Input: S = β000001β , T = β11β
Output: NO
Approach:
- It can be observed that only initial N β M + 1 elements of S can be modified (else length of S would not be equal to T).
- Therefore, the substring S[N β M + 2]β¦S[N] must be equal to T[2]β¦T[M]
- And for the first element of T, if it is 0, min operation can be used on the elements of S.
- Else, the max operation can be used.
So it would be sufficient to check whether any of the initial N β M + 1 elements of S equals first element of T.
Based on the above observation, the following approach can be used to solve the problem :
- If the length of S is less than the length of T, return false.
- Iterate from i = 1 to M β 1 and check if S[i + N β M] is equal to T[i] at each iteration. If not so, return false.
- Iterate from 0 to N β M and check if S[i] is equal to T[0] at any iteration and above conditions are satisfied, return true.
Below is the implementation of this approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible to // convert a string into another string by // doing the given operation bool isPossible(string S, string T) { int N = S.size(), M = T.size(); // If size of S is less than size of T, // then the conversion is not possible if (N < M) { return false ; } // Checking if the substring // S(N + M - 2...N) is equal to // T(1...M) for ( int i = 1; i < M; i++) { if (S[i + N - M] != T[i]) { return false ; } } // Checking if any element in the // substring S(0..N-M+1) is // equal to T[0] for ( int i = 0; i < N - M + 1; i++) { if (S[i] == T[0]) { return true ; } } return false ; } // Driver Code int main() { string S = "001001" ; string T = "11" ; // Function Call bool answer = isPossible(S, T); if (answer == true ) { cout << "YES" ; } else { cout << "NO" ; } } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to check if it is possible to // convert a string into another string by // doing the given operation public static boolean isPossible(String S, String T) { int N = S.length(), M = T.length(); // If size of S is less than size of T, // then the conversion is not possible if (N < M) { return false ; } // Checking if the substring // S(N + M - 2...N) is equal to // T(1...M) for ( int i = 1 ; i < M; i++) { if (S.charAt(i + N - M) != T.charAt(i)) { return false ; } } // Checking if any element in the // substring S(0..N-M+1) is // equal to T[0] for ( int i = 0 ; i < N - M + 1 ; i++) { if (S.charAt(i) == T.charAt( 0 )) { return true ; } } return false ; } // Driver Code public static void main(String[] args) { String S = "001001" ; String T = "11" ; // Function Call boolean answer = isPossible(S, T); if (answer == true ) { System.out.print( "YES" ); } else { System.out.print( "NO" ); } } } // This code is contributed by Rohit Pradhan |
Python3
# Python3 code for the above approach # Function to check if it is possible to # convert a string into another string by # doing the given operation def isPossible(S, T) : N = len (S); M = len (T); # If size of S is less than size of T, # then the conversion is not possible if (N < M) : return False ; # Checking if the substring # S(N + M - 2...N) is equal to # T(1...M) for i in range ( 1 , M) : if (S[i + N - M] ! = T[i]) : return False ; # Checking if any element in the # substring S(0..N-M+1) is # equal to T[0] for i in range (N - M + 1 ) : if (S[i] = = T[ 0 ]) : return True ; return False ; # Driver Code if __name__ = = "__main__" : S = "001001" ; T = "11" ; # Function Call answer = isPossible(S, T); if (answer = = True ) : print ( "YES" ); else : print ( "NO" ); # This code is contributed by AnkThon |
C#
// C# code for the above approach using System; class GFG { // Function to check if it is possible to // convert a string into another string by // doing the given operation public static bool isPossible( string S, string T) { int N = S.Length, M = T.Length; // If size of S is less than size of T, // then the conversion is not possible if (N < M) { return false ; } // Checking if the substring // S(N + M - 2...N) is equal to // T(1...M) for ( int i = 1; i < M; i++) { if (S[i + N - M] != T[i]) { return false ; } } // Checking if any element in the // substring S(0..N-M+1) is // equal to T[0] for ( int i = 0; i < N - M + 1; i++) { if (S[i] == T[0]) { return true ; } } return false ; } // Driver Code public static void Main(String[] args) { String S = "001001" ; String T = "11" ; // Function Call bool answer = isPossible(S, T); if (answer == true ) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } // This code is contributed by Tapesh (tapeshdua420) |
Javascript
<script> // Javascript code for the above approach // Function to check if it is possible to // convert a string into another string by // doing the given operation function isPossible(S, T) { let N = S.length, M = T.length; // If size of S is less than size of T, // then the conversion is not possible if (N < M) { return false ; } // Checking if the substring // S(N + M - 2...N) is equal to // T(1...M) for (let i = 1; i < M; i++) { if (S[i + N - M] != T[i]) { return false ; } } // Checking if any element in the // substring S(0..N-M+1) is // equal to T[0] for (let i = 0; i < N - M + 1; i++) { if (S[i] == T[0]) { return true ; } } return false ; } // Driver Code let S = "001001" ; let T = "11" ; // Function Call let answer = isPossible(S, T); if (answer == true ) { document.write( "YES" ); } else { document.write( "NO" ); } // This code is contributed by saurabh_jaiswal. </script> |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us