Programa C++ para encontrar el número máximo de ceros colocados consecutivamente al principio y al final en cualquier rotación de una string binaria

Dada una string binaria S de tamaño N , la tarea es maximizar la suma de la cuenta de 0 s consecutivos presentes al principio y al final de cualquiera de las rotaciones de la string dada S .

Ejemplos:

Entrada: S = “1001”
Salida: 2
Explicación:
Todas las rotaciones posibles de la string son:
“1001”: Cuenta de 0s al inicio = 0; al final = 0. Suma= 0 + 0 = 0.
“0011”: Cuenta de 0s al inicio = 2; al final = 0. Suma = 2 + 0=2
“0110”: Cuenta de 0s al inicio = 1; al final = 1. Suma= 1 + 1 = 2.
“1100”: Cuenta de 0s al inicio = 0; al final = 2. Suma = 0 + 2 = 2
Por lo tanto, la suma máxima posible es 2.

Entrada: S = “01010”
Salida: 2
Explicación: 
Todas las rotaciones posibles de la string son:
“01010”: Cuenta de 0s al inicio = 1; al final = 1. Suma= 1+1=1
“10100”: Cuenta de 0s al inicio = 0; al final = 2. Suma= 0+2=2
“01001”: Cuenta de 0s al inicio = 1; al final = 0. Suma= 1+0=1
“10010”: Cuenta de 0s al inicio = 0; al final = 1. Suma= 0+1=1
“00101”: Cuenta de 0s al inicio = 2; al final = 0. Suma= 2+0=2
Por lo tanto, la suma máxima posible es 2.

Enfoque ingenuo: la idea más simple es generar todas las rotaciones de la string dada y, para cada rotación, contar el número de 0 presentes al principio y al final de la string y calcular su suma. Finalmente, imprima la suma máxima obtenida.  

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of a string present in any
// of the rotations of the given string
void findMaximumZeros(string str, int n)
{
    // Check if all the characters
    // in the string are 0
    int c0 = 0;
  
    // Iterate over characters
    // of the string
    for (int i = 0; i < n; ++i) {
        if (str[i] == '0')
            c0++;
    }
  
    // If the frequency of '1' is 0
    if (c0 == n) {
  
        // Print n as the result
        cout << n;
        return;
    }
  
    // Concatenate the string
    // with itself
    string s = str + str;
  
    // Stores the required result
    int mx = 0;
  
    // Generate all rotations of the string
    for (int i = 0; i < n; ++i) {
  
        // Store the number of consecutive 0s
        // at the start and end of the string
        int cs = 0;
        int ce = 0;
  
        // Count 0s present at the start
        for (int j = i; j < i + n; ++j) {
            if (s[j] == '0')
                cs++;
            else
                break;
        }
  
        // Count 0s present at the end
        for (int j = i + n - 1; j >= i; --j) {
            if (s[j] == '0')
                ce++;
            else
                break;
        }
  
        // Calculate the sum
        int val = cs + ce;
  
        // Update the overall
        // maximum sum
        mx = max(val, mx);
    }
  
    // Print the result
    cout << mx;
}
  
// Driver Code
int main()
{
    // Given string
    string s = "1001";
  
    // Store the size of the string
    int n = s.size();
  
    findMaximumZeros(s, n);
  
    return 0;
}

2

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es encontrar el número máximo de ceros consecutivos en la string dada . Además, encuentre la suma de 0 s consecutivos al principio y al final de la string, y luego imprima el máximo de ellos. 
Siga los pasos a continuación para resolver el problema:

• Compruebe si la frecuencia de ‘1’ en la string, S es igual a 0 o no. Si es cierto, imprima el valor de N como resultado.
• De lo contrario, realice los siguientes pasos:
  • Almacene el número máximo de 0s consecutivos en la string dada en una variable, digamos X .
  • Inicialice dos variables, comience como 0 y finalice como N-1 .
  • Incrementa el valor de cnt y empieza por 1 mientras que S[start] no es igual a ‘ 1 ‘.
  • Incrementa el valor de cnt y decrementa end en 1 mientras que S[end] no es igual a ‘ 1 ‘.
  • Imprime el máximo de X y cnt como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of any rotation of the string str
void findMaximumZeros(string str, int n)
{
    // Stores the count of 0s
    int c0 = 0;
    for (int i = 0; i < n; ++i) {
        if (str[i] == '0')
            c0++;
    }
  
    // If the frequency of '1' is 0
    if (c0 == n) {
  
        // Print n as the result
        cout << n;
        return;
    }
  
    // Stores the required sum
    int mx = 0;
  
    // Find the maximum consecutive
    // length of 0s present in the string
    int cnt = 0;
  
    for (int i = 0; i < n; i++) {
        if (str[i] == '0')
            cnt++;
        else {
            mx = max(mx, cnt);
            cnt = 0;
        }
    }
  
    // Update the overall maximum sum
    mx = max(mx, cnt);
  
    // Find the number of 0s present at
    // the start and end of the string
    int start = 0, end = n - 1;
    cnt = 0;
  
    // Update the count of 0s at the start
    while (str[start] != '1' && start < n) {
        cnt++;
        start++;
    }
  
    // Update the count of 0s at the end
    while (str[end] != '1' && end >= 0) {
        cnt++;
        end--;
    }
  
    // Update the maximum sum
    mx = max(mx, cnt);
  
    // Print the result
    cout << mx;
}
  
// Driver Code
int main()
{
    // Given string
    string s = "1001";
  
    // Store the size of the string
    int n = s.size();
  
    findMaximumZeros(s, n);
  
    return 0;
}

2

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

Consulte el artículo completo sobre la cantidad máxima de 0 colocados consecutivamente al principio y al final de cualquier rotación de una string binaria para obtener más detalles.