Periodic Binary String With Minimum Period and a Given Binary String as Subsequence.

0 0 4 minutes read

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, S_i is equal to S_{i +}_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 period
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)
        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 Code
int main()
{
    string S = "1111001";
    findPeriodicString(S);
    return 0;
}

Java

// Java implementation to find the
// periodic string with minimum period
class GFG{
     
// Function to find the periodic string
// with minimum period
static 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 Code
public 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 period
def 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 Code
if __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 period
static 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 period
function 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 Code
let S = "1111001";
findPeriodicString(S);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output:

10101010101010

Time Complexity: O(N)
Auxiliary Space: O(2*N)

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 zambiatek!