Generar string binaria con el mismo número de subsecuencia 01 y 10

Dado un número entero N (N > 2), la tarea es generar una string binaria de tamaño N que consta de números iguales de subsecuencias » 10 » y » 01 » y también la string debe contener al menos un ‘0’ y un ‘ 1’

Nota: Si existen varias strings de este tipo, imprima cualquiera.

Ejemplos: 

Entrada: 4
Salida: 0110
Explicación: aquí, la string 0110 consta de la misma cantidad de
subsecuencias ’01’ y ’10’ y consta de al menos una aparición de 0 y 1.

Entrada: 3
Salida: 010
Explicación: aquí, la string 010 consta de la misma cantidad de subsecuencias ’01’ y ’10’ 
y consta de al menos una aparición de 0 y 1.

Enfoque ingenuo: 

La idea es generar todas las strings binarias posibles (string que consta solo de 0 y 1) y encontrar una substring con el mismo número de subsecuencias ’01’ y ’10’.

Complejidad de tiempo: O(2 ^N * 2 ^N ) = O(4 ^N ) porque cada string también tiene 2 ^N subsecuencias.
Espacio Auxiliar: O(N)

Enfoque eficiente: para resolver el problema, siga las siguientes observaciones:

Caso 1 (si N es par): luego agregue 1 en el índice N/2 y (N/2 – 1), y agregue 0 al resto de la string. Entonces, el conteo de ’10’ y ’01’ será el mismo, lo que equivale a 2*(N/2 – 1) = (N – 2) y la string también consta de al menos una ocurrencia de 0 y 1.

Por ejemplo:

• Si N = 4, eso significa que N es par, luego agregue 1 en el índice N/2 = 2 y (N/2)-1 = 1. 
• Y agregue 0 en las posiciones restantes de 0 a 3.
• Por lo tanto, la string es «0110».

Caso 2 (si N es impar): luego agregue 1 en el medio y agregue 0 al resto de la string. Entonces, el conteo de ’10’ y ’01’ es el mismo que es igual a N/2 y la string también consiste al menos una vez en la ocurrencia de 0 y 1.

Por ejemplo:

• Si N=3, eso significa que N es impar, luego agregue 1 en el índice N/2=1.
• Y agregue 0 en las posiciones restantes de 0 a 2.
• Por lo tanto, la string es «010».

Siga los pasos a continuación para implementar el enfoque anterior:

• Tome una string vacía s .
• Ahora comprueba si N es par o impar:
  • Si N es par, itere de 0 a N – 1 y agregue ‘1’ solo en el índice N/2 y (N/2 – 1) y ‘0’ en los otros índices de la string.
  • Si N es impar, itere de 0 a N-1 y agregue ‘1’ solo en el índice N/2 y ‘0’ en todos los demás índices de la string.
• Ahora, devuelva la string construida.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
string makeString(int n)
{
    string s = "";
 
    // If n is even then follow this block
    int mid = n / 2;
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
 
            // If i is at middle of n and
            // previous middle of n
            // then add 1 into the string
            if (i == mid || i == mid - 1) {
                s += "1";
            }
 
            // Otherwise, add 0 to the string
            else {
                s += "0";
            }
        }
    }
 
    // If n is odd then follow this block
    else {
        for (int i = 0; i < n; i++) {
 
            // If i is equal to mid then
            // add 1 to the string
            if (i == mid) {
                s += "1";
            }
 
            // Otherwise add 0 to the string
            else {
                s += "0";
            }
        }
 
        // Return the constructed string
        return s;
    }
}
 
// Driver code
int main()
{
    int N = 4;
 
    // Function call
    cout << makeString(N);
    return 0;
}

// Java code to implement the approach
 
 
import java.util.*;
 
class GFG{
 
static String makeString(int n)
{
    String s = "";
 
    // If n is even then follow this block
    int mid = n / 2;
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
 
            // If i is at middle of n and
            // previous middle of n
            // then add 1 into the String
            if (i == mid || i == mid - 1) {
                s += "1";
            }
 
            // Otherwise, add 0 to the String
            else {
                s += "0";
            }
        }
    }
 
    // If n is odd then follow this block
    else {
        for (int i = 0; i < n; i++) {
 
            // If i is equal to mid then
            // add 1 to the String
            if (i == mid) {
                s += "1";
            }
 
            // Otherwise add 0 to the String
            else {
                s += "0";
            }
        }
 
        // Return the constructed String
        return s;
    }
    return s;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4;
 
    // Function call
    System.out.print(makeString(N));
}
}
 
// This code contributed by shikhasingrajput

0110

Complejidad temporal: O(N)
Espacio auxiliar: O(N)