Find the shortest Binary string containing one or more occurrences of given strings
Given two Binary strings, S1 and S2, the task is to generate a new Binary strings (of least length possible) which can be stated as one or more occurrences of S1 as well as S2. If it is not possible to generate such a string, return -1 in output. Please note that the resultant string must not have incomplete strings S1 or S2.
For example, “1111” can be the resultant string for “11” and “1111” as it is 1 occurrence of “1111” and can also be judged as two occurrences of “11”.
Examples:
Input: S1 = “1010”, S2 = “101010”
Output: 101010101010
Explanation: The resultant string is 3 occurrences of s1 and 2 occurrences of s2.Input: S1 = “000”, S2 = “101”
Output: -1
Explanation: There is no way possible to construct such a string.
Approach: If it is possible to make such a string, then it’s length will be the LCM of lengths of strings S1 and S2. Because only then, it can be stated as a minimum multiple of string S1 and S2. Follow the steps below to solve the problem:
- Define a function repeat(int k, string S) and perform the following tasks:
- Initialize the string r as an empty string.
- Iterate over the range [0, K] and perform the following steps:
- Append the string S to the variable r.
- Return the string r as the answer.
- Initialize the variables x and y as the lengths of the strings S1 and S2.
- Initialize the variable gcd as the GCD of x and y.
- Call the function repeat(y/gcd, s1) to form the string S1 that many times and store that into the variable A.
- Call the function repeat(x/gcd, s2) to form the string S2 that many times and store that into the variable B.
- If A is equal to B, then print any one of them as the answer, else print “NO”.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to form the resultant string string repeat( int k, string S) { string r = "" ; while (k--) { r += S; } return r; } // Function to find if any such string // exists or not. If yes, find it void find(string s1, string s2) { int x = s1.size(), y = s2.size(); // GCD of x and y int gcd = __gcd(x, y); // Form the resultant strings string A = repeat(y / gcd, s1); string B = repeat(x / gcd, s2); // If both the strings are same, // then print the answer if (A == B) { cout << A; } else { cout << "-1" ; } } // Driver Code int main() { // Initializing strings string s1 = "1010" , s2 = "101010" ; find(s1, s2); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { public static int GCD( int a, int b) { // Everything divides 0 if (a == 0 ) return b; if (b == 0 ) return a; // base case if (a == b) return a; // a is greater if (a > b) return GCD(a - b, b); return GCD(a, b - a); } public static String repeat( int k, String S) { String r = "" ; while (k--!= 0 ) { r += S; } return r; } // Function to find if any such string // exists or not. If yes, find it public static void find(String s1, String s2) { int x = s1.length(), y = s2.length(); // GCD of x and y int gcd = GCD(x, y); // Form the resultant strings String A = repeat(y / gcd, s1); String B = repeat(x / gcd, s2); // If both the strings are same, // then print the answer if (A.equals(B)) { System.out.println(A); } else { System.out.println( "-1" ); } } // Driver Code public static void main(String[] args) { // Initializing strings String s1 = "1010" , s2 = "101010" ; find(s1, s2); } } // This code is contributed by maddler. |
Python3
# Python program for the above approach import math # Function to form the resultant string def repeat(k, S): r = "" while (k): r + = S k - = 1 return r # Function to find if any such string # exists or not. If yes, find it def find(s1, s2): x = len (s1) y = len (s2) # GCD of x and y gcd = math.gcd(x, y) # Form the resultant strings A = repeat(y / / gcd, s1) B = repeat(x / / gcd, s2) # If both the strings are same, # then print answer if (A = = B): print (A) else : print ( "-1" ) # Driver Code # Initializing strings s1 = "1010" s2 = "101010" find(s1, s2) # This code is contributed by shivanisinghss2110 |
C#
// C# program for the above approach using System; class GFG{ public static int GCD( int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return GCD(a - b, b); return GCD(a, b - a); } public static string repeat( int k, string S) { string r = "" ; while (k--!=0) { r += S; } return r; } // Function to find if any such string // exists or not. If yes, find it public static void find( string s1, string s2) { int x = s1.Length, y = s2.Length; // GCD of x and y int gcd = GCD(x, y); // Form the resultant strings string A = repeat(y / gcd, s1); string B = repeat(x / gcd, s2); // If both the strings are same, // then print the answer if (A.Equals(B)) { Console.Write(A); } else { Console.Write( "-1" ); } } // Driver Code public static void Main() { // Initializing strings string s1 = "1010" , s2 = "101010" ; find(s1, s2); } } // This code is contributed by code_hunt. |
Javascript
<script> // Javascript program for the above approach function GCD(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return GCD(a - b, b); return GCD(a, b - a); } // Function to form the resultant string function repeat(k, S) { var r = "" ; while (k-- != 0) { r += S; } return r; } // Function to find if any such string // exists or not. If yes, find it function find(s1, s2) { var x = s1.length, y = s2.length; // GCD of x and y var gcd = GCD(x, y); // Form the resultant strings var A = repeat(y / gcd, s1); var B = repeat(x / gcd, s2); // If both the strings are same, // then print the answer if (A == B) { document.write(A); } else { document.write( "-1" ); } } // Driver Code // Initializing strings var s1 = "1010" , s2 = "101010" ; find(s1, s2); // This code is contributed by shivanisinghss2110 </script> |
101010101010
Time Complexity: O(m + n + log(max(m, n)))
Auxiliary Space: O(n) (For storing the strings A & B)
Contact Us