Periodic Binary String: A Binary string is called periodic if it can be written as a repetition of a binary string of smaller or same length. For example, 101010 is a periodic binary string with period 10 as we can get the string by repeatedly appending 10 to itself. In general, the string S with period P means, Si is equal to Si + P.
Problem: Given a binary string S, the task is to find the periodic string with minimum possible period with the following additional conditions
1) The given string S should be a subsequence of the result
2) Length of the result should not be more than twice the length of input string.
Examples:
Input:S = “01”
Output:0101
Explanation:The output string has period as 2 and has given string as subsequence.Input :S = “111”
Output :111
Explanation:The output string has period as 1.Input:S = “110”
Output: 101010
Explanation:The output string has period as 2 and has given string as subsequence. Please note that 110110 is not answer because the period length is more.
Approach:
The main idea depends on two possibilities:
- If the string consists all 1s or all 0s, the answer is the given string S itself having period as 1.
- If the string consists of dissimilar elements, find the string with period 2 and having length as twice the length of given string S
Below is the implementation of the above approach:
C++
// C++ implementation to find the// periodic string with minimum period#include <bits/stdc++.h>using namespace std;// Function to find the periodic string// with minimum periodvoid findPeriodicString(string S){ int l = 2 * S.length(); int count = 0; for (int i = 0; i < S.length(); i++) { if (S[i] == '1') count++; } // Print the string S if it // consists of similar elements if (count == S.length() || count == 0) cout << S << "\n"; // Find the required periodic // string with period 2 else { char arr[l]; for (int i = 0; i < l; i += 2) { arr[i] = '1'; arr[i + 1] = '0'; } for (int i = 0; i < l; i++) cout << arr[i]; cout << "\n"; }}// Driver Codeint main(){ string S = "1111001"; findPeriodicString(S); return 0;} |
Java
// Java implementation to find the// periodic string with minimum periodclass GFG{ // Function to find the periodic string// with minimum periodstatic void findPeriodicString(String S){ int l = 2 * S.length(); int count = 0; for(int i = 0; i < S.length(); i++) { if (S.charAt(i) == '1') count++; } // Print the string S if it // consists of similar elements if (count == S.length() || count == 0) System.out.println(S); // Find the required periodic // string with period 2 else { char arr[] = new char[l]; for(int i = 0; i < l; i += 2) { arr[i] = '1'; arr[i + 1] = '0'; } for(int i = 0; i < l; i++) System.out.print(arr[i]); System.out.println(); }}// Driver Codepublic static void main (String[] args){ String S = "1111001"; findPeriodicString(S);}}// This code is contributed by chitranayal |
Python3
# Python3 implementation to find the# periodic with minimum period# Function to find the periodic string# with minimum perioddef findPeriodicString(S): l = 2 * len(S) count = 0 for i in range(len(S)): if (S[i] == '1'): count += 1 # Print the S if it # consists of similar elements if (count == len(S) or count == 0): print(S) # Find the required periodic # with period 2 else: arr = ['0']*l for i in range(0, l, 2): arr[i] = '1' arr[i + 1] = '0' for i in range(l): print(arr[i],end="")# Driver Codeif __name__ == '__main__': S = "1111001" findPeriodicString(S) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the// periodic string with minimum period using System;class GFG{ // Function to find the periodic string// with minimum periodstatic void findPeriodicString(string S){ int l = 2 * S.Length; int count = 0; for(int i = 0; i < S.Length; i++) { if (S[i] == '1') count++; } // Print the string S if it // consists of similar elements if (count == S.Length || count == 0) Console.WriteLine(S); // Find the required periodic // string with period 2 else { char[] arr = new char[l]; for(int i = 0; i < l; i += 2) { arr[i] = '1'; arr[i + 1] = '0'; } for(int i = 0; i < l; i++) Console.Write(arr[i]); Console.WriteLine(); }}// Driver code public static void Main () { string S = "1111001"; findPeriodicString(S);} } // This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript implementation to find the// periodic string with minimum period// Function to find the periodic string// with minimum periodfunction findPeriodicString(S){ let l = 2 * S.length; let count = 0; for(let i = 0; i < S.length; i++) { if (S[i] == '1') count++; } // Print the string S if it // consists of similar elements if (count == S.length || count == 0) document.write(S + "<br>"); // Find the required periodic // string with period 2 else { let arr = new Array(l); for(let i = 0; i < l; i += 2) { arr[i] = '1'; arr[i + 1] = '0'; } for(let i = 0; i < l; i++) document.write(arr[i]); document.write("<br>"); }}// Driver Codelet S = "1111001";findPeriodicString(S);// This code is contributed by avanitrachhadiya2155</script> |
10101010101010
Time Complexity: O(N)
Auxiliary Space: O(2*N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
