Máximo 1 contiguo posible en una string binaria después de k rotaciones

Dada una string binaria, puede rotar cualquier substring de esta string. Por ejemplo, permita que la string se denote por s. Deje que el primer elemento de la string esté representado por s[0], el segundo elemento esté representado por s[1] y así sucesivamente.
s = «100110111»

Supongamos que rotamos la substring comenzando desde s[2] y terminando en s[4]. Entonces la string después de esta operación será:
String resultante = “101100111”

Ahora, puede realizar como máximo k operaciones para rotar cualquier substring. Tienes que decir el número máximo de 1 contiguos que puedes hacer en esta string en k o menos de k rotaciones de substring.

Ejemplos:

Entrada: 100011001
k = 1
Salida: 3
Explicación:
k es 1, por lo tanto, solo puede rotar una vez. Gire la substring comenzando desde s[1] y terminando en s[5]. La string resultante será: 111000001. Por lo tanto, el máximo de 1 contiguos es 3.

Entrada: 001100111000110011100
k = 2
Salida: 8
Explicación:
k es 2, por lo que puede rotar dos veces. Gire la substring que comienza en s[6] y termina en s[15]. String resultante después de la primera rotación: 001100001100011111100. Luego, rote la substring que comienza en s[8] y termina en s[12]. String resultante después de la segunda rotación: 001100000001111111100. Por lo tanto, el número máximo de 1 contiguos es 8.

Concepto para resolver:
Para resolver este problema, mantendremos la frecuencia de los 1 en la parte de los 1 contiguos en la string original en un conjunto múltiple. Luego, en cada rotación, rotaremos esa substring de manera que 2 porciones de 1 contiguo (con la frecuencia máxima) en la string se unan. Haremos esto, ordenando el conjunto múltiple del elemento más grande al más pequeño. Eliminaremos los 2 elementos superiores de multiset e insertaremos su suma nuevamente en el multiset. Continuaremos haciendo esto hasta que se completen k rotaciones o el número de elementos en multiset se reduzca a 1.

// C++ program to calculate maximum contiguous
// ones in string
#include <bits/stdc++.h>
using namespace std;
  
// function to calculate maximum contiguous ones
int maxContiguousOnes(string s, int k)
{
  
    int i, j, a, b, count;
  
    // multiset is used to store frequency  of 
    // 1's of each portion of contiguous 1 in 
    // string in decreasing order
    multiset<int, greater<int> > m;
  
    // this loop calculate all the frequency
    // and stores them in multiset
    for (i = 0; i < s.length(); i++) {
        if (s[i] == '1') {
            count = 0;
            j = i;
            while (s[j] == '1' && j < s.length()) {
                count++;
                j++;
            }
            m.insert(count);
            i = j - 1;
        }
    }
  
    // if their is no 1 in string, then return 0
    if (m.size() == 0)
        return 0;
  
    // calculates maximum contiguous 1's on
    // doing rotations
    while (k > 0 && m.size() != 1) {
  
        // Delete largest two elements
        a = *(m.begin()); 
        m.erase(m.begin()); 
        b = *(m.begin()); 
        m.erase(m.begin()); 
  
        // insert their sum back into the multiset
        m.insert(a + b); 
        k--;
    }
  
    // return maximum contiguous ones 
    // possible after k rotations
    return *(m.begin());
}
  
// Driver code
int main()
{
    string s = "10011110011";
    int k = 1;
    cout << maxContiguousOnes(s, k);
    return 0;
}

6