String binaria periódica con período mínimo y una string binaria dada como subsecuencia.

String binaria periódica : una string binaria se llama periódica si se puede escribir como repetición de una string binaria de menor o igual longitud. Por ejemplo, 101010 es una string binaria periódica con período 10, ya que podemos obtener la string agregando 10 repetidamente a sí misma. En general, la string S con período P significa que S _i es igual a S _{i + P} . 

Problema: Dada una string binaria S , la tarea es encontrar la string periódica con el período mínimo posible con las siguientes condiciones adicionales 
1) La string S dada debe ser una subsecuencia del resultado 
2) La longitud del resultado no debe ser más del doble la longitud de la string de entrada.

Ejemplos: 

Entrada: S = “01” 
Salida: 0101 
Explicación: La string de salida tiene un período de 2 y ha dado una string como subsecuencia.

Entrada: S = “111” 
Salida: 111 
Explicación: La string de salida tiene un período de 1.

Entrada: S = “110” 
Salida: 101010 
Explicación: La string de salida tiene un período de 2 y ha dado una string como subsecuencia. Tenga en cuenta que 110110 no es una respuesta porque la duración del período es mayor.

Enfoque: 
La idea principal depende de dos posibilidades:

1. Si la string consta de todos los 1 o todos los 0, la respuesta es la misma string dada S que tiene un período como 1 .
2. Si la string consta de elementos diferentes, encuentre la string con período 2 y que tenga una longitud del doble de la longitud de la string dada S

A continuación se muestra la implementación del enfoque anterior: 

// 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 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 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# 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

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

10101010101010

Complejidad de tiempo : O(N)