Maximice las particiones en una string binaria dada que tenga la misma proporción de 0 y 1

Dada una string binaria S de tamaño N , la tarea es encontrar el número máximo de particiones de la string S tal que la proporción del número de 0 y 1 en todas las particiones sea la misma.

Ejemplos: 

Entrada: S = “010100001”
Salida: 3
Explicación: 
La substring [0, 2], [3, 5] y [6, 8] tienen la misma proporción de ‘ 0′ y ‘1’ es 2:1. Por lo tanto, la partición máxima posible es 3.

Entrada: str=”001101″
Salida: 2

Enfoque ingenuo: el enfoque ingenuo es generar todas las particiones de la string S y encontrar la partición que tiene una frecuencia máxima de 0 a 1 .
Complejidad temporal: O(N*2 ^N )
Espacio auxiliar: O(N)

Enfoque eficiente: para resolver este problema, primero vea algunas observaciones:

Digamos que hay dos strings de prefijos que obtienen la misma proporción de 0 y 1 . Entonces es posible dividir el prefijo más grande en dos con la misma proporción. Por ejemplo, S = “0101”, el prefijo [0, 1] tiene una proporción de 1:1 y el prefijo [0, 3] tiene una proporción de 1:1 , entonces es posible dividir la string en dos con la proporción 1: 1 Por lo tanto, solo cuente la cantidad de prefijos que tienen la misma proporción de 0 y 1 que la string S e imprima la cantidad de prefijos con esa proporción.

Siga los pasos a continuación para resolver el problema: 

• Inicialice dos variables enteras, digamos count_of_0 y count_of_1 como 0 para almacenar el recuento del número de caracteres ‘0’ y ‘1’ respectivamente.
• Inicialice un mapa hash , digamos M , que almacena la frecuencia de la relación de ‘ 0′ a ‘ 1′ .
• Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
  • Si S[i] es igual a ‘0’, entonces incremente el recuento_de_0 en 1, de lo contrario, incremente el recuento_de_1 en 1 .
  • Encuentra el GCD de count_of_0 y count_of_1 y guárdalo en una variable, digamos GCD .
  • Si GCD = 0 , entonces incremente m[{count_of_0, count_of_1}] en 1 .
  • Si GCD != 0 , aumente el valor de m[{count_of_0 / GCD, count_of_1 / GCD}] en 1 .
• Imprime el valor de m[{count_of_0 / GCD, count_of_1 / GCD}] como respuesta.

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 maximum partition such
// that the ratio of 0 and 1 are same
void maximumPartition(string S)
{
  
    // Size of string
    int N = S.size();
  
    // Variable to store the frequency
    // of 0 and 1
    int count_of_0 = 0, count_of_1 = 0;
  
    // Map to store frequency of ratio
    map<pair<int, int>, int> m;
  
    int ans;
  
    // Traverse the string
    for (int i = 0; i < N; i++) {
        // Increment the frequency
        // of 0 by 1 if s[i] = 0
        if (S[i] == '0')
            count_of_0++;
        // Otherwise increment frequency of 1
        else
            count_of_1++;
  
        int first = count_of_0, second = count_of_1;
  
        // Find GCD of count_of_0 and count_of_1
        int GCD = __gcd(count_of_0, count_of_1);
  
        // Convert the count of 0 and count of 1
        // in the coprime numbers
        if (GCD != 0) {
            first = count_of_0 / GCD;
            second = count_of_1 / GCD;
        }
  
        // Increase the ratio of 0 and 1 by 1
        m[{ first, second }]++;
        ans = m[{ first, second }];
    }
  
    cout << ans << endl;
}
  
// Driver Code
int main()
{
    // Given Input
    string S = "001101";
  
    // Function Call
    maximumPartition(S);
    return 0;
}

2

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